AOJ 2885 - 分割統治
解法
まず、問題の条件を満たすようなパターンについて整理します。1つめのサンプルを見てみると、例えば下のようなパターンがあり得ます。
青が太郎、黄色が次郎、緑が花子さんの統治している国になります。
結局のところ、
太郎君(花子さん)が統治している街に隣接している全ての街は、次郎君が統治している
次郎君が統治している街に隣接している全ての街は、太郎君(花子さん)が統治している
ということで、二部グラフです。
最終的にやることは、2つの頂点集合の個数を調べ、それぞれ、頂点の個数が偶数だった場合に、その半分が答えになります。
そもそも二部グラフになっていなければ、答えは存在しません。
頂点の個数がどちらも偶数だった場合は、その個数がどちらも同じであった場合はで答えを出力し、異なっていたならば、
で、昇順に答えを出力すればよいです。
二部グラフの頂点の個数は、始点となる頂点を1つ決め、そこからBFSをして、始点からの距離の偶奇を見ればよいです。
感想
あまりICPCっぽくない気がしました(経験があまりないのでなんとも言えませんが)。
今回は、問題の条件を整理した時点で方針がパッと見えたので、すんなり解けました。とりあえず図におこしてみるとわかりやすいですね。
