题目描述

我们有一张包含 $N$ 个点和 $M$ 条边的简单无向图。 这些点的编号分别为 $1, 2, \cdots, N$，这些边的编号分别为 $1, 2, \cdots, M$。第 $i$ 条边连接点 $A_i$ 和点 $B_i$ 。

求出在这个图上为每个点染上红，绿，蓝三种颜色使之满足以下条件的染色方案数：

• 由一条边直接相连的两点的颜色总是不同

这里不强制使用所有颜色。

限制：

• $1 \leqslant N \leqslant 20$
• $1 \leqslant M \leqslant \frac{N(N-1)}{2}$
• $1 \leqslant A_i \leqslant N$
• $1 \leqslant B_i \leqslant N$
• 给定的图为简单图

算法

(DFS) $O(n*2^{n - 1})$

对于每个连通分量，当确定了其中某点 $x$ 的颜色之后，与 $x$ 直接相连的点最多有 2 种可以染的颜色，所以我们仅需要搜索 $3 \times 2^{n - 1}$ 种染色方式。其中 $n$ 是连通分量中点的个数。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

int n;
vector<vector<int>> to;

vector<int> used, col;
vector<int> vs;
void dfs(int v) {
    if (used[v]) return;
    used[v] = 1;
    vs.push_back(v);
    for (int u : to[v]) dfs(u);
}

ll now;
void dfs2(int i) {
    if (i == vs.size()) { now++; return; }
    int v = vs[i];
    rep(c, 3) {
        col[v] = c;
        bool ok = true;
        for (int u : to[v]) {
            if (col[u] == c) ok = false;
        }
        if (!ok) continue;
        dfs2(i + 1);
    }
    col[v] = -1;
}

int main() {
    int m;
    cin >> n >> m;
    to = vector<vector<int>>(n);

    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }

    ll ans = 1;
    used = vector<int>(n);
    col = vector<int>(n, -1);
    rep(i, n) {
        if (used[i]) continue;
        ans *= 3;
        vs = vector<int>();
        dfs(i);
        col[vs[0]] = 0;
        now = 0;
        dfs2(1);
        ans *= now;
    }

    cout << ans << '\n';

    return 0;
}