ARC105 - E Keep Graph Disconnected

ARC105-Eを解いた,

問題

与えられた $N$ 頂点 $M$ 辺のグラフに対して先手と後手が辺を追加していく.しかし、頂点 $1$ と頂点 $N$ を連結にするような辺は追加できない.操作できなくなったら敗北、敗北しなかった方の勝利.
両者が最適に行動したときに勝利するのはどちらか.

解法

グラフの連結成分が二つで、頂点 $1$ を含む連結成分と $N$ を含む連結成分がそれぞれ完全グラフである状態で手番が回ってきた人は負ける. また、最終的なグラフが定まっていればその辺数と $M$ が勝敗が容易に判断できる.
ここで $N$ が奇数であれば、最終的に頂点 $1$ を含む連結成分のサイズを $x(1 \leq x \leq N-1)$ とすると、 $x(N-x)$ 辺が最終的に追加されないが、これは常に奇数であることから容易にどちらの勝利か判定できる.
$N$ が偶数の場合は、最終的な $x$ の偶奇によって勝敗が定まる(片方は最終的に $x$ を偶数にしたい、もう片方は $x$ を奇数にしたいという状況になる). 最初に頂点 $1$ と連結である頂点の数を $a$ として、同様に $b$ を頂点 $N$ について定める.
$c:=(a \, mod \, 2) + (b \, mod \, 2)$
と置き、この値によって場合分けする.
1. $c=0$ の場合
最終的に $x$ を偶数にしたい方の勝利( $N$ が偶数よりサイズが奇数の連結成分の個数は偶数個、よって相手の操作を打ち消すような操作が確実にできる).
2. $c=2$ の場合
最終的に $x$ を奇数にしたい方の勝利(証明は1の場合と同じ).
3. $c=1$ の場合
先手の勝利( $N$ が偶数よりサイズが奇数の連結成分は奇数個、よって自分の有利な方に動かす方で1,2の場合に帰着できる).

よってUnionFindなどを用いて $a,b$ を求めれば答えが求まる.