ABC199 D - RGB Coloring 2
まず、赤色となる頂点を全て決めます。
sukesan1984.iconok (全部赤に塗るときもあると）
各頂点について赤であるか否かの2通りが考えられる為、全部で$ 2^N通りの選び方があります。
sukesan1984.iconわかる
赤色の頂点同士が辺で結ばれている場合、条件を満たさない為0通りとして数えます。
sukesan1984.iconわかる
次に、全ての赤色となる頂点選び方における縁、青色の塗り分けについて考えます。
sukesan1984.iconいいでしょう
もし、赤色でない頂点とその頂点同士を結ぶ辺を抜き出したグラフ(誘導部分グラフ)がニ部グラフで無いなら二色に塗り分ける事ができない為、0通りとして数えます。
sukesan1984.icon？？？？？
赤色でない頂点とその頂点同士を結ぶ辺を抜き出したグラフ
また、二ニ部グラフである場合、連結成分の内一番頂点番号の小さい頂点の色が決まれば連結成分全体の色が決まるため、連結成分の数をSとして、$ 2^S通りとして数えることが出来ます。
これはいくつかの部分集合にわけられるのかな。
それぞれが独立してるので、2部グラフであるなら、最初の頂点が決められれば、全部の色が決まるので、青か緑の2通り
分けられる独立数分だけ考えて$ 2^Sになると。
よって二部グラフ判定や、連結成分判定をAtCoder Library のdsuで行った場合、$ O(\alpha(N)N^22^N)(但し、アッカーマン関数をAとした時、$ \alpha(x)は $ A(x, x)の逆関数)で解くことが出来ます。
DFS等を使用することで$ O(N^22^N)で解くことも可能です。
参考にした