与えられたグラフは奇閉路を持たないため、連結成分はそれぞれ二部グラフとなります。そこで、グラフに対して、次の 5 つの特徴量を考えます。

• \(x\) ： 連結性を変化させることなく、二部性を保ったまま追加することができる辺の個数
• \(\mathrm{ee}\) ： 2つの部集合の頂点数がどちらも偶数であるような連結成分の個数
• \(\mathrm{oo}\) ： 2つの部集合の頂点数がどちらも奇数であるような連結成分の個数
• \(\mathrm{eo}\) ： 2 つの部集合の頂点数が偶数と奇数であるような連結成分であり、頂点数 \(2\) 以上の連結成分の個数
• \(\mathrm{iso}\)：頂点数 \(1\) の連結成分の個数

このとき、勝敗判定は以下のように行えます。

• \(N\) が奇数のとき
  • \(\mathrm{oo}+x\) が奇数なら先手勝ち、偶数なら後手勝ち
• \(N\) が偶数かつ \(\mathrm{eo}=0\) のとき
  • \(\mathrm{iso}/2+x\) が奇数なら先手勝ち、偶数なら後手勝ち
• \(N\) が偶数かつ \(1 \leq \mathrm{eo}\leq 2\) のとき
  • 先手勝ち
• \(N\) が偶数かつ \(\mathrm{eo} \geq 3\) のとき
  • \(\mathrm{oo}+x\) が奇数なら先手勝ち、偶数なら後手勝ち

証明のアイディア

このゲームでは操作ごとにグラフの辺が1つ増えていくため、最終的なグラフでの辺の個数の偶奇性が重要となります。
\(N\) が奇数のとき、ゲーム終了時の二部グラフの部集合の頂点数は、一方が奇数、他方が偶数となるので、グラフに含まれる辺の個数は必ず偶数です。よって、操作によらず現在の辺の個数のみによって勝敗が決まります。
\(N\) が偶数のとき、ゲーム終了時の二部グラフの部集合の頂点数が、ともに偶数となるかともに奇数となるかによって、辺の個数の偶奇が変わります。最終的なグラフの部集合のサイズの偶奇を変化させる要因は、\(\mathrm{eo}\) 及び \(\mathrm{iso}\) に寄与する連結成分のマージの仕方のみなので、これらを適切に扱うことが本質です。

証明

\(N\) が奇数のとき

このとき、ゲーム終了時のグラフに含まれる辺の個数は操作によらず必ず偶数であるため、現在のグラフに含まれる辺の個数のみによって勝敗が定まる。現在のグラフに含まれる連結成分の個数は \(偶数\times 偶数\times\mathrm{ee} + 奇数\times 奇数\times\mathrm{oo}+偶数\times 奇数\times\mathrm{eo}-x\) であるから、この偶奇は \(\mathrm{oo}+x\) の偶奇に等しい。よってこれが奇数ならば先手勝ち、偶数ならば後手勝ちである。

\(N\) が偶数かつ \(\mathrm{eo}=0\) のとき

このとき、\(\mathrm{iso}\) は偶数であることに注意する。
\(\mathrm{iso}/2+x\) が奇数ならば、\(\mathrm{iso}/2\) と \(x\) のどちらかは正なので、孤立点同士を結ぶ辺を追加するか、連結性を変えない辺を追加することができる。これにより「\(\mathrm{eo}=0\) かつ \(\mathrm{iso}/2+x\) が偶数」という状態にすることができる。
\(\mathrm{iso}/2+x\) が偶数ならば、行える操作は

• 連結性を変えない辺を追加する
• 孤立点同士を結ぶ辺を追加する
• 孤立点でない連結成分同士を結ぶ辺を追加する
  
• 孤立点と他の連結成分を結ぶ辺を追加する

のいずれか。1,2,3番目の操作後は「\(\mathrm{eo}=0\) かつ \(\mathrm{iso}/2+x\) が奇数」となる。4番目の操作では、(まだ孤立点が残っていることに注意して)次の手番に相手が同じ連結成分に孤立点とを結ぶ辺を適切に追加した場合、再び「\(\mathrm{eo}=0\) かつ \(\mathrm{iso}/2+x\) が偶数」の状態で手番が回ってくる。

ゲームの終了条件を満たすとき \(\mathrm{eo}=\mathrm{iso}=x=0\) であることに注意すると、辺の個数の帰納法によりこのケースでは「\(\mathrm{iso}/2+x\) が奇数」であることが先手勝ちであるための必要十分条件であることがわかる。

\(N\) が偶数かつ \(\mathrm{eo}=1\) のとき

頂点数の偶奇性から孤立点が少なくとも \(1\) つ存在する。\(\mathrm{eo}\) に寄与する連結成分と孤立点を結ぶ辺を適切に追加することで、操作後に「\(\mathrm{eo}=0\) かつ \(\mathrm{iso}/2+x\) が偶数」となるようにすることができる。

\(N\) が偶数かつ \(\mathrm{eo}=2\) のとき

\(\mathrm{eo}\) に寄与する連結成分同士を結ぶ辺を適切に追加することで、操作後に「\(\mathrm{eo}=0\) かつ \(\mathrm{iso}/2+x\) が偶数」となるようにすることができる。

\(N\) が偶数かつ \(\mathrm{eo}\geq 3\) のとき

1回の操作では \(\mathrm{eo}\) は高々 \(2\) しか変化しないことから、自身の操作後に \(\mathrm{eo} < 3\) となった場合、既に示したように負けとなる。よって \(\mathrm{eo}\) に寄与する連結成分を常に \(3\) 個残した状態でゲームを進めた場合と勝敗は一致する。これにより \(N\) が奇数のケースに帰着された。