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

問題文

http://codeforces.com/contest/576/problem/B

解法

自分は直感で、どうせ p に周期3以上のサイクルがあると困るんじゃないの、みたいに考えた。
周期3以上のサイクル内部で辺を張るとループができて困るので、そういう意味では正しい。
また、2つのサイクル c1 = (a1, a2, ..., ak), c2 = (b1, b2, ..., bm) があって、それらのうちから1つのペアを選んで結んでいくと、当然 a1-b1, a2-b2, ... のようにどんどん組まれていくことになる。
なので、k と m の長さが互いに素だとループができて困るなあということもわかる。

そして最も重要なこととして、こうして結んでできた連結成分の構造というのは、あるサイクルに含まれる頂点ごとに注目すると全く同じである。
つまり、ある段階で a1, a2, ... が属する連結成分をそれぞれ見ると、全く同じグラフになっているということ。
これと、木の中心はたかだか2個しかないという性質から、以下のことがわかる。
「周期1または2のサイクルがない場合、構築不可能である」
周期3以上のサイクル内の頂点が中心になるとすると、他の頂点もすべて中心になっているはずなので、それは矛盾だからである。

・周期1のサイクルがある場合
その頂点を他の全部の頂点と結べばOK
・周期1のサイクルがなく、周期2のサイクルがある場合
周期が互いに素だと困るなあ、というのはここで使う。つまり、周期が奇数のサイクルがあれば構築不可能であり、そうでなければ交互に結んでいけばOK。
例えば (a1, a2) と (b1, b2, b3, b4) があれば (a1, b1), (a2, b2), (a1, b3), (a2, b4) と辺を作る。
このときにサイクルの順番は崩さないように。union_find でサイクルを求めてしまって、順番が壊れたまま構築するとWAになる（僕はやらかしました、詰めが甘いね）。

これで解ける。オーダーは O(N)

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int n; cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; ++i) {
        cin >> p[i];
        p[i]--;
    }

    vector<bool> visited(n);
    function<void(int, vector<int>& vs)> dfs = [&] (int v, vector<int>& vs) {
        if(visited[v]) return;
        visited[v] = true;
        vs.push_back(v);
        dfs(p[v], vs);
    };
    vector<vector<int>> cmp;
    int sz1_v = -1;
    int sz2_cmp = -1, odd = 0;
    for(int i = 0; i < n; ++i) {
        if(visited[i]) continue;
        vector<int> vs;
        dfs(i, vs);
        if(vs.size() == 1u) {
            sz1_v = i;
        }
        if(vs.size() == 2u) {
            sz2_cmp = cmp.size();
        }
        odd += vs.size() & 1;
        cmp.push_back(move(vs));
    }
    if(sz1_v != -1) {
        cout << "YES" << endl;
        for(int i = 0; i < n; ++i) {
            if(i == sz1_v) continue;
            cout << sz1_v + 1 << ' ' << i + 1 << endl;
        }
    } else if(sz2_cmp != -1 && odd == 0) {
        cout << "YES" << endl;
        cout << cmp[sz2_cmp][0] + 1 << ' ' << cmp[sz2_cmp][1] + 1 << endl;
        for(int i = 0; i < (int)cmp.size(); ++i) {
            if(sz2_cmp == i) continue;
            for(int j = 0; j < (int)cmp[i].size(); j += 2) {
                cout << cmp[sz2_cmp][0] + 1 << ' ' << cmp[i][j] + 1 << endl;
                cout << cmp[sz2_cmp][1] + 1 << ' ' << cmp[i][j + 1] + 1 << endl;
            }
        }
    } else {
        cout << "NO" << endl;
    }
}

感想

時間内に解けなかった。
解説に "It's easy to notice, that centers of that tree must turn into centers after applying the permutation. That means, permutation must have cycle with length 1 or 2 since there're at most two centers" と書いてあって、最初な～にが easy じゃとなっていた。
union find 使って失敗したのも反省（当たり前なのにね、意外と気づかなかった）。