以下ではAliceがBobを有限ターンで捕まえることが出来ることをAliceの勝ち、 それ以外の時をBobの勝ちと表記します。

今回の問題で与えられるグラフは \(N\) 頂点 \(N\) 辺の連結グラフであり、これはなもりグラフと呼ばれます。 なもりグラフの各連結成分は1つのサイクルおよびサイクル上の頂点の根とした木から構成されます。

今回BobがAliceから逃げ切るためには、サイクル上の頂点に移動し、 Aliceの行動に合わせてサイクル上の頂点を移動する必要があります。 (木の部分にいると袋小路が存在するためAliceに追い詰められてしまいます。) またサイクルの大きさが3以下だとどのようにしてもAliceにつかまってしまいます。

一方AliceはBobが最初木の部分にいる場合は、その木からBobがサイクルに出てこないように行動することで、 Bobを捕まえることが可能です。

以上のことから

• サイクルの大きさが3の時、Aliceの勝ち。(制約からサイクルの大きさが1,2になることはありません。)
• Bobの初期位置 \(b\) がサイクル上にある時、 Aliceの初期位置 \(a\) と \(b\) が隣接していなければBobの勝ち。
• Bobの初期位置 \(b\) がサイクル上にない時、Bobがいる木の根の頂点を \(s\) と置くと、 \(d(b,s) + 1 < d(a,s)\) となるときBobの勝ち。

となります。(\(d(u,v)\) は頂点 \(u\) と頂点 \(v\) の最短経路の長さを示す。) ここで、 \(d(b,s) + 1 = d(a,s)\) の時はBobのターンが終わった時点で、 頂点 \(s\) にBobが、その隣接頂点にAliceがいるような形にできるため、次に操作できるAliceの勝ちとなります。

なもりグラフのサイクルの検出は \(O(N)\) 、 なもりグラフ上での最短経路はBFSを行うことで \(O(N)\) で解くことが出来るので、 本問題を \(O(N)\) で解くことが出来ました。

クレジット

原案： nu50218

解法： nu50218

問題準備・解説： Jinapetto

レビュー： US_cube

テスター： QCFium

校正： nu50218