Namori Grundy [AtCoder Regular Contest 079 F]

http://arc079.contest.atcoder.jp/tasks/arc079_d

前提知識

• 必須ではないが grundy数

解法

http://arc079.contest.atcoder.jp/submissions/1471649

今回はgrundy数と同様の決め方で頂点に数を割り振っていくので、grundy数を理解していると、より分かりやすい。

まず、葉から順に幅優先で処理していきながら、数を確定できる所は先に確定しておく（pre関数）。
すると、確定していない所はサイクルになっている。

確定していない所のうち、1つを選ぶ(fixid変数)。
少し考えてみると、そこで確定する可能性のある数は2種類しかない。
それは、grundy数として一番小さいもの(fir)と二番目に小さいもの(sec)である。

サイクル内のある頂点の数を確定させると、全体の数が確定するので、可能性のある2通りに対して、実際に代入、構築してみて、全体で整合性が取れているかを確認する。
取れていれば"POSSIBLE"、どちらでも取れない場合は"IMPOSSIBLE"

int N;
vector<int> E[201010];
int P[201010];
int A[201010];
//---------------------------------------------------------------------------------------------------
void pre() { // 葉を刈る
    queue<int> que;
    rep(i, 1, N + 1) if (E[i].size() == 0) que.push(i);
    while (!que.empty()) {
        int cu = que.front(); que.pop();
        if (0 <= A[cu]) continue;

        set<int> s;
        int ng = 0;
        fore(to, E[cu]) {
            if (A[to] < 0) ng = 1;
            s.insert(A[to]);
        }

        if (ng) continue;

        int g = 0;
        while (s.count(g)) g++;

        A[cu] = g;
        que.push(P[cu]);
    }
}
//---------------------------------------------------------------------------------------------------
bool check(int i, int x) {
    int pre = x;
    int cu = P[i];
    while (cu != i) {
        set<int> s;
        s.insert(pre);
        fore(to, E[cu]) s.insert(A[to]);
        int g = 0;
        while (s.count(g)) g++;
        pre = g;
        cu = P[cu];
    }

    set<int> s;
    s.insert(pre);
    fore(to, E[i]) s.insert(A[to]);
    int g = 0;
    while (s.count(g)) g++;
    
    return g == x;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N + 1) {
        int p; cin >> p;
        E[p].push_back(i);
        P[i] = p;
    }
    rep(i, 1, N + 1) A[i] = -1;

    pre();

    int fixid = 0;
    rep(i, 1, N + 1) if (A[i] < 0) fixid = i;

    set<int> s;
    fore(to, E[fixid]) s.insert(A[to]);
    int fir = 0;
    while (s.count(fir)) fir++;
    int sec = fir + 1;
    while (s.count(sec)) sec++;

    string ans = "IMPOSSIBLE";
    if (check(fixid, fir)) ans = "POSSIBLE";
    else if (check(fixid, sec)) ans = "POSSIBLE";

    cout << ans << endl;
}