AT_abc199_d 题解

· · 题解

思路

因为 n 很小，可以考虑 dfs 暴力涂色。

直接枚举的复杂度为 O(3^n)，不能通过。

我们可以将图拆分为多个连通分块，单独计算每个分块的方案数，最终结果即为所有分块的方案数之积。

代码便是两个 dfs 函数，一个用于拆分连通块，一个用于计算分块的方案数。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<int> G[30];
int vis[N], c[N];
int cnt;
vector<int> a;

void dfs1(int u) {
    a.push_back(u);
    vis[u] = 1;
    for (int v : G[u]) {
        if (vis[v]) continue;
        dfs1(v);
    }
}

void dfs2(int u) {
    if (u == a.size()) {
        cnt++;
        return;
    }
    int x = a[u];
    int flag[4] = {0};
    for (auto v : G[x]) flag[c[v]] = 1;
    for (int i = 1; i <= 3; i++) {
        if (flag[i]) continue;
        c[x] = i;
        dfs2(u + 1);
        c[x] = 0;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        a.clear();
        dfs1(i);
        cnt = 0;
        dfs2(0);
        ans = ans * cnt;
    }
    cout << ans;
    return 0;
}