複数の解法が存在するため、その中から \(3\) 通りの解法を紹介します。

解法1 公式解説の解法

公式解説をご覧下さい。

実装例

解法2 色を1色のみ固定する方法

まず、赤色となる頂点を全て決めます。各頂点について赤であるか否かの \(2\) 通りが考えられる為、全部で \(2^N\) 通りの選び方があります。赤色の頂点同士が辺で結ばれている場合、条件を満たさない為 \(0\) 通りとして数えます。

次に、全ての赤色となる頂点選び方における緑、青色の塗り分けについて考えます。もし、赤色でない頂点とその頂点同士を結ぶ辺を抜き出したグラフ(誘導部分グラフ)が二部グラフで無いなら二色に塗り分ける事ができない為、 \(0\)通りとして数えます。また、二部グラフである場合、連結成分の内一番頂点番号の小さい頂点の色が決まれば連結成分全体の色が決まるため、連結成分の数を \(S\) として、 \(2^S\) 通りとして数えることが出来ます。

よって二部グラフ判定や、連結成分判定をAtCoder Library のdsuで行った場合、 \(\mathcal{O}(\alpha(N) N^22^N)\) (但し、アッカーマン関数を\(A\) とした時、 \(\alpha(x)\) は \(A(x,x)\)の逆関数) で解くことが出来ます。

DFS等を使用することで\(\mathcal{O}(N^2 2^N)\)で解くことも可能です。

実装例: dsu, DFS

解法3 subset convolution を使用する方法

subset convolution というテクニックを使用することでも解くことが出来ます。

赤く塗る頂点の集合を \(R\) 、緑色に塗る頂点の集合を \(G\) 、緑色に塗る頂点の集合を \(B\) とします。それぞれの集合に含まれる頂点同士が辺で結ばれておらず、全ての頂点が集合 \(R,G,B\) のどれか一つにのみ必ず含まれている事が必要十分であるため、これを数える事を考えます。まず、どれか一つに含まれるという条件を緩和し同じ頂点が \(R,G,B\) の内、複数の集合に入れる事が出来るが、どれかには入っていなければならないとすると、これは or convolution (zeta変換/mobius変換) を用いて解くことが出来ます。 ここで、重複の判定は難しい為、次のように言い換えます。

• 全ての頂点が \(R,G,B\) の内少なくともどれか一つの集合に入っており、\(|R|+|G|+|B| = N\)

これを計算するには多項式をor convolutionで畳み込む事で出来ますが、ここで考慮される多項式は\(\mathcal{O}(N)\) 次式と非常に小さい為、フーリエ変換による高速化を使用せずとも十分高速に動作し、 \(\mathcal{O}(N^2 2^N)\) で解くことが出来ます。

実装例

おまけ 高速な手法

Fomin, F. V., Gaspers, S., & Saurabh, S. (2007, July). Improved exact algorithms for counting 3-and 4-colorings. In International Computing and Combinatorics Conference (pp. 65-74). Springer, Berlin, Heidelberg.

によると\(\mathcal{O}(1.6262^N)\)で解くことも可能なようです