ARC079 F : Namori Grundy(800)
作成日：2017.07.30
最終更新日：2017.07.30
問題概要
$1$から$N$の番号が振られた$N$個の頂点と$p_i$から$i$へ入り込む$N$本の辺$(p_i,i)$からなる弱連結な有向グラフが与えられる。
各頂点$v$に非負整数$a_v$を割り当てる時、2つの条件「辺$(i,j)$が存在するならば$a_i \neq a_j$」、
「すべての頂点$i$と$0 \leq x < a_i$を満たす整数$x$において、辺$(i,j)$が存在する頂点$j$で$x=a_j$となるものが存在」を満たすようにしたい。
これが可能であるかを判定せよ。
制約
$2 \leq N \leq 2 \times 10^5$
$1 \leq p_i \leq N$
$p_i \neq i$
グラフは弱連結
考え方
サンプルを図示するとサイクルが必ず1つだけできることに気付く。
これは各頂点に入っていく辺の数は1つであることとグラフが弱連結であることから、
出ていく辺のない頂点を削除したグラフを次々に考えていくと、これらのグラフも問題で与えられ得るグラフであることから分かる。
まず、与えられた条件を言い換えることを考える。
2つ目の条件は、$a_i$が頂点$i$から出ていく辺の先の頂点に割り当てる数に依存することを示している。
1つ目の条件をそのように解釈しても等価であることから、与えられた条件は「ある頂点$i$に割り当てられる数は、その頂点から出ていく辺の先の頂点に割り当てられた数の集合に現れない最小の非負整数」と言い換えることができる。
サイクルに含まれていない頂点を考えると、先の言い換えから順次$a_i$を定めることができることが分かる。
次にサイクルに含まれる頂点を考えるが、これは順次決められるとは限らない。
そこで、まずは簡単のためにサイクルに含まれる頂点からの寄与を無視して$a_i$を定め、後からサイクルを考慮することにする。
つまり、サイクルを考慮していく時に$a_i$が更新され得る条件を考えれば良い。
$a_i$が更新された場合必ず大きくなることから、その条件は頂点から出る辺でサイクルを構成するものの先の頂点の方が暫定的に割り当てられている数が大きいか等しいことである。
これを満たさない頂点が存在するならば、その頂点から順次$a_i$を定めることができる。
そうでない時は、すなわちサイクル中の頂点に暫定的に割り当てられた数がすべて等しい時である。
この時、割り当てられる数が更新されるものとされないものは交互に現れるはずである。
しかし、サイクルを構成する頂点の数が奇数であるときそれは不可能である。
逆にそれが偶数であるならば可能である。
ソースコード
マクロ等はこちら
const int MC = 200010;
int N;
int p[MC];
vector<int> V[MC];
vector<int> d[MC];
int a[MC]; //暫定的に割り当てられた数
bool b[MC];
bool c[MC]; //サイクル内の頂点ならtrue
int r;
int dfs(int q){
for(auto u : V[q]){
if(c[u]) continue;
d[q].PB(dfs(u));
}
sort(d[q].begin(),d[q].end());
a[q] = -1;
for(auto u : d[q]){
if(u > a[q]+1) break;
a[q] = u;
}
return ++a[q];
}
int main(){
scanf("%d" , &N);
repp(i,1,N+1){
scanf("%d" , p + i);
V[p[i]].PB(i);
}
r = 1;
while(!b[r]){
b[r] = 1;
r = p[r];
}
while(!c[r]){
c[r] = 1;
r = p[r];
}
repp(i,1,N+1){
if(c[i]) dfs(i);
}
bool t = 0;
int y = 0;
while(c[r]){
c[r] = 0;
if(a[r] != a[p[r]]) t = 1;
r = p[r];
++y;
}
printf("%s\n" , t || y%2==0 ? "POSSIBLE" : "IMPOSSIBLE");
return 0;
}解法まとめ
サイクルに含まれる頂点を1つ求める。(31-35行)
サイクルを構成する頂点を求める。(36-39行)
$a_i$を暫定的に割り当て、サイクル中の頂点に対しその最小値を求める。(11-23,40-42行)
サイクル中の頂点の$a_i$の暫定的な値がすべて等しく、その要素数が奇数の時に限り不可能。(43-51行)