Codeforces Round #347 (Div. 1) C. Graph Coloring

辺に R or G の色を持つ無向グラフが与えられる。ひとつ頂点を選んで、その頂点に接続している辺の色を反転する操作を繰り返しおこない辺の色を統一したい。

操作回数が最小になる方法をひとつ示せ。

R に揃える場合と B に揃える場合をそれぞれ解いてみて、小さい方を採用する。R に揃えることを考えてみよう。

それぞれの頂点を 2 回以上反転するのは無意味なので、0 回か 1 回の反転だけを考えればいい。反転する頂点を黒で塗ることにすると、辺の両端の色はそれぞれ次のようになる。

したがって一つ頂点の色を決めると連鎖的に他の頂点の色も決まる。

白と黒の役割を入れ替えても条件を満たすので、反転する回数が少なくなる方の色を使えばいい。

今回はグラフが連結とは限らないので、各連結成分に対してこの作業を繰り返す必要がある。

連結性を勝手に仮定してしまい 1WA。Union-Find を使って 2-SAT を解く方法もある。