Graph Game (UVa Live Archive Asia - 2009 Ningbo)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=353&page=show_problem&problem=2761

問題

頂点数n、辺数mのグラフが与えられる。このグラフ上で二人でゲームをする。各手番で先手はグラフの辺を赤に塗り、後手は青に塗る。後手は青い辺だけを見た時に連結グラフにすることができたら勝利である。どちらが勝つか求めよ。
1<=n<=10
0<=m<=30

解法

辺を縮約しながら探索。多重辺が出てきたらその瞬間にそこは縮約すること*1。

*1:先手が多重辺の片方を塗ったら、後手はその多重辺を塗り替えすと多重辺が縮約されていることを除き先手が色を塗る前と同じ状況になり後手が有利になるから。