No.038 D

※ コードは WA が取れてない

ある数 $x$ を考え, A さんが $x$ 以上を取れるなら A さんの勝ちとする. このようになる最大の $x$ を二分探索で求める.

グラフの頂点を手番で分け, その頂点, 手番の組で手番の人が勝てる場合は黒, 手番の人が負ける場合は白として色分けしていく.

手番が A さんで頂点に書かれている数が $x$ 以上の場合, および手番が B さんで頂点に書かれている数が $x$ 未満の場合は黒になる. また, ある頂点の行き先がなければ終了宣言するしかないので, その頂点が黒でなければ白になる.

そして, ある頂点の行き先の頂点がすべて黒ならばその頂点は白となり, 行き先に白の頂点がひとつでもあればその頂点は黒となる. 行き先の頂点がすべて黒かどうかは, その頂点の行き先の黒の個数を数えておき, それが頂点の出次数と一致するかどうかを見る.

こうして $1$ の頂点で A さんの手番の勝ち負けを見る.

なお $1$ の頂点の勝ち負けが決まらない場合はループしているので, この場合は後手に選択権があり, B さんの勝ちとする.