問題atcoder.jp連結とは限らない単純無向グラフであって、二部グラフであるものが与えられる。二部グラフでなくならないように交互に辺を 1 本ずつ追加していき、そのような操作ができなくなったほうが負けとなるゲームの勝敗を判定する問題である。解法atcoder.jpMMNMM さんのユーザ解説の方法で解く。この記事では、青木くんおよび高橋くんという呼び方は使わず、先手と後手で統一する。このゲームでは 1 手ごとに必ず辺が 1 本ずつ追加される。したがって、先手番の後の辺数の偶奇は必ず \(M\) と異なり、後手番の後の辺数の偶奇は必ず \(M\) と等しくなる。また、ゲームが終了した時点でグ…
