四色问题C++

四问题是一个经典的计算机科学问题，它要求在给定的地图上为每个区域着色，并且相邻的区域必须使用不同的颜色。这个问题可以使用图论算法来解决。

以下是一个用C++实现的四色问题程序：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100; // 最大的区域数
int n, m; // n 是区域数，m 是边数
bool g[MAXN][MAXN]; // 用邻接矩阵表示图
int color[MAXN]; // color[i] 表示第 i 个区域的颜色
vector<int> adj[MAXN]; // 用邻接表表示图

// 检查第 k 个区域是否可以着色为 c
bool check(int k, int c) {
    for (int i = 0; i < adj[k].size(); i++) {
        int j = adj[k][i];
        if (color[j] == c) {
            return false;
        }
    }
    return true;
}

// 递归搜索
bool dfs(int k) {
    if (k == n) {
        // 所有区域都着色完毕，输出结果
        for (int i = 0; i < n; i++) {
            cout << color[i] << " ";
        }
        cout << endl;
        return true;
    }
    for (int i = 1; i <= 4; i++) {
        if (check(k, i)) {
            color[k] = i;
            if (dfs(k+1)) {
                return true;
            }
            color[k] = 0;
        }
    }
    return false;
}

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

这个程序使用了邻接矩阵和邻接表两种表示图的方法。它首先读入地图的信息，然后使用邻接矩阵和邻接表分别表示图。

在搜索过程中，程序通过递归枚举每个区域可以使用的颜色，然后检查相邻的区域是否已经着色，如果相邻的区域已经使用了当前颜色，那么就跳过这个颜色，继续枚举下一个颜色。如果所有的颜色都尝试过了，仍然没有找到满足要求的颜色，则回溯到上一个区域，重新尝试着色。如果所有的区域都已经着色完毕，则输出结果。