ABC199 D RGB Coloring
この問題は考察パートも実装パートも重いABC-Dにしては非常に難しい問題である.
考察パート
$ N \leq 20であるので, $ O(3^N)(愚直な3彩色)は間に合わない. そこで連結成分ごとに分けて考えてみる. ある連結成分について, 連結であるという性質を使うと, ある1頂点を決めてしまえば, その頂点に隣接する頂点から塗っていくことで使える色は2色以下になるので, その連結成分についてはサイズを$ sとすると$ O(2^s)で解けることがわかる. 以上より, (実装さえできれば)この問題を$ O(2^N N)で解くことができた.
実装パート
塗っていく過程が難しい.
方針としては, 連結成分を検出するためにグラフを探索するDFSを書き, さらに検出した連結成分に番号を付け, その順番に塗っていくDFSを書く. 順番はDFS順につければよい.