四色问题 C++

四色问题是一个著名的地图着色问题，它要求在地图上用四种颜色对相邻的区域进行着色，使得相邻的区域颜色不同，求出最小的着色数。这个问题可以使用图论中的图染色算法来解决。

以下是一个使用C++语言实现的四色问题代码：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
int n, m, ans = MAXN;
vector<int> g[MAXN];
int color[MAXN];

void dfs(int cur, int cnt) {
    if (cur > n) {
        ans = min(ans, cnt);
        return;
    }
    // 尝试给当前节点染色
    for (int i = 1; i <= 4; i++) {
        int j;
        for (j = 0; j < g[cur].size(); j++) {
            int k = g[cur][j];
            if (color[k] == i) break;
        }
        if (j == g[cur].size()) {
            color[cur] = i;
            dfs(cur + 1, cnt + 1);
            color[cur] = 0;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

其中，`g`是邻接表，表示图中的边；`color`是节点的颜色，初始为0表示未染色；`dfs`函数是深度优先搜索，依次尝试给每个节点染色，并检查相邻节点是否有相同的颜色。如果当前节点染色后不会与相邻节点冲突，则继续搜索下一个节点；否则尝试其他颜色。当染色完成后更新最小着色数`ans`。最后输出`ans`即可。

需要注意的是，实现中使用了剪枝操作，即如果当前节点染色后会与相邻节点冲突，则直接跳过当前颜色的尝试，因为其他节点也会尝试这个颜色，所以不必重复计算。