Codeforces Round #319 (Div. 1) B. Invariance of Tree

問題

codeforces.com

解法

まず前提知識です。順列は必ずサイクルの集合で表すことが出来ます。例えば,
2 1 4 3
という順列を考えると, この順列は,
1 <-> 2
3 <-> 4
の交換によって表現されます。これは, (1, 2) というサイクルと (3, 4) というサイクルの集合で表せます。また, 例えば
6, 5, 4, 3, 1, 2
という順列を考えると, この順列は,
3 <-> 4
1 -> 6 -> 2 -> 5 (-> 1 -> 6 -> ...)
というふたつの数字交換で表せます。なので, (3, 4) というサイクルと (1, 6, 2, 5) というサイクルの集合で表せることになります。

この知識を使って問題を解いてみます。実は, サイクルの長さ(カッコの中に含まれる数字の数) が 2 以下のものが少なくとも 1 つはないと絶対に木を作ることは出来ません。まずはこの理由を考えます。

すべてのサイクルが 3 以上のとき, 自分のサイクルの中で辺を結ぼうとすると, 問題文の条件を満たそうとすると閉路が出来てしまいます。例えば, (i, j, k) というサイクルができているとしましょう。
i - j の間に辺を結ぶと, j - k の間にも辺を結ぶことになります(順列で考えると i 番目の数字が j で j 番目の数字が k になっているので)。で, j - k の間に辺を結ぶと同じようにして k と i の間にも辺を結ぶことになります。ということで,
i -> j -> k -> i
という閉路が出来てしまうことになり, 詰みです。また, i, j, k の間に辺を結ばないことにすると, 連結にするためには例えば
i -> (他のサイクルの点 a) -> ... -> j
とかしなければなりませんが, こうすると
j -> (他のサイクルの点 b) -> ... -> k
k -> (他のサイクルの点 c) -> ... -> i
となり結局閉路ができています。

以上により, すべてのサイクルが 3 以上の時は木が作れないことがわかりました。

では サイクルが 1 の点(つまり i == p[i] となる点)がある場合を考えます(この点を a とする)。この場合は簡単で, a と他の点を結べば OK です。

次にサイクルが 2 の点(i == p[p[i]])がある場合を考えます(a, b とする)。この場合は, 他のサイクルはすべて偶数で, それぞれのサイクルの偶数番目の頂点は a と, 奇数番目の頂点は b と結ばれるようにすれば OK です。

得た知見

• 順列はサイクルに分割できる
  • ここで サイクル -> ループ という考えはすぐ出来たほうが良さそう
  • 木の条件を考える時ループがないか考えるのは普通だからね

const int MAXN = 100010;
int p[MAXN];
bool used[MAXN];

void solve(int n) {
    int index1 = -1, index2 = -1;
    for (int i = 0; i < n; i++) {
        if (i == p[i]) {
            index1 = i;
            break;
        } else if (i == p[p[i]]) {
            index2 = i;
        }
    }
    if (index1 != -1) {
        cout << "YES" << endl;
        for (int i = 0; i < n; i++) {
            if (i == index1) continue;
            cout << i+1 << " " << index1+1 << endl;
        }
        return;
    } else if (index2 != -1) {
        vector<pii> ans;
        used[index2] = used[p[index2]] = true;
        ans.emplace_back(index2, p[index2]);
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            vector<int> v;
            int cur = i;
            while (1) {
                if (used[cur]) break;
                used[cur] = true;
                v.push_back(cur);
                cur = p[cur];
            }
            int size = v.size();
            if (size%2) {
                cout << "NO" << endl;
                return;
            } else {
                for (int i = 0; i < size; i++) {
                    if (i%2 == 0) ans.emplace_back(index2, v[i]);
                    else ans.emplace_back(p[index2], v[i]);
                }
            }
        }
        cout << "YES" << endl;
        for (auto p : ans) {
            cout << p.first+1 << " " << p.second+1 << endl;
        }
        return;
    } else cout << "NO" << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    solve(n);
    return 0;
}