ARC087 F Namori Grundy

問題文

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

 

どの頂点も入次数が1であることから,グラフの形は以下のような「なもりグラフ」になる.

f:id:Div9851P:20180822165818j:plain

入次数が1であるから,どの頂点についても「親」を定義することが出来る(同様に「子」も定義する).

まず簡単な場合としてグラフが有向木(根つき木の無向辺を親→子の向きに向き付けして有向グラフにしたもの)であるときをかんがえると,子に割り当てられた整数が全てわかっていれば親に割り当てる整数も決まるので再帰的に計算すれば全ての頂点に割り当てる値が一意に定まる(常に割り当てられる).

元の問題に戻ると,輪の周りに生えている木のところについては上の方法で割り当てる値を計算しておいて,あとは輪の上にある適当な頂点を選んでその頂点に割り当てる値を全て試せばよい(1つ決めればさっきと同様にして輪の上にある頂点に割り当てる値は全て決まる).

ちなみに輪を見つけるには「適当な頂点からスタートして親をたどっていくと,どこかで同じ頂点が現れる.二回現れた頂点の間に出てきたのが輪」というアルゴリズムを用いればいい(どこかで見たことがあった).

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
int par[200000];
vector<int> out[200000];
int pos[200000];
set<int> s[200000];
int dfs(int v) {
    set<int> s;
    for (int to : out[v]) s.insert(dfs(to));
    int x = 0;
    while (s.find(x) != s.end()) x++;
    return x;
}
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> par[i];
        par[i]--;
        out[par[i]].push_back(i);
    }
    vector<int> vec;
    memset(pos, -1, sizeof(pos));
    pos[0] = 0;
    vec.push_back(0);
    int now = par[0];
    while (pos[now] == -1) {
        pos[now] = vec.size();
        vec.push_back(now);
        now = par[now];
    }
    int p = pos[now];
    for (int i = p; i < vec.size(); i++) {
        int prev;
        if (i == p) prev = vec.size() - 1;
        else prev = i - 1;
        for (int to : out[vec[i]]) {
            if (to == vec[prev]) continue;
            s[vec[i]].insert(dfs(to));
        }
    }
    vec.push_back(vec[p]);
    for (int i = 0; i <= out[vec[p]].size(); i++) {
        int x = i;
        for (int j = p + 1; j < vec.size(); j++) {
            int y = 0;
            while (y == x || s[vec[j]].find(y) != s[vec[j]].end()) y++;
            x = y;
        }
        if (x == i) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
}