回溯法解决图的m着色问题c++

图的m着色问题是指对于一个无向图，给定m种颜色，要求给每个节点染上一种颜色，并且相邻的节点不能染相同的颜色。可以使用回溯法来解决该问题。

具体思路如下：

1.从任意一个节点开始，尝试给该节点染上第一种颜色。

2.检查该节点与已染色节点的相邻节点的颜色是否相同。如果相同，则回溯到上一个节点，尝试给该节点染上第二种颜色。如果第二种颜色也不行，则回溯到上一个节点，继续尝试其它颜色。

3.如果所有颜色都尝试了，但都不能满足条件，则回溯到上一个节点，重新尝试其它颜色。

4.重复步骤2和3，直到所有节点都染色完毕，或者无解。

代码实现如下（假设有一个无向图，节点从0到n-1标号）：

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

const int MAXN = 1005;

int n, m; // n为节点数，m为颜色数
int color[MAXN]; // 存储染色方案
bool g[MAXN][MAXN]; // 存储图的邻接矩阵

bool dfs(int u) {
    if (u == n) return true; // 所有节点都染色完毕
    for (int i = 1; i <= m; i++) { // 枚举所有颜色
        bool ok = true;
        for (int j = 0; j < n; j++) { // 检查与已染色节点相邻的节点
            if (g[u][j] && color[j] == i) {
                ok = false;
                break;
            }
        }
        if (ok) { // 可以染上该颜色
            color[u] = i;
            if (dfs(u + 1)) return true; // 继续染色
            color[u] = 0; // 回溯
        }
    }
    return false; // 无解
}

int main() {
    memset(g, false, sizeof(g));
    memset(color, 0, sizeof(color));
    cin >> n >> m;
    int x, y;
    while (cin >> x >> y) {
        g[x][y] = g[y][x] = true; // 无向图
    }
    if (dfs(0)) { // 染色成功
        for (int i = 0; i < n; i++) {
            cout << color[i] << " ";
        }
        cout << endl;
    } else { // 染色失败
        cout << "No solution" << endl;
    }
    return 0;
}

在上述代码中，dfs函数的参数u表示当前要染色的节点编号，dfs函数返回值为bool类型，表示是否能够染色成功。在dfs函数中，使用for循环枚举所有颜色，然后检查该颜色是否符合要求。如果可以染上该颜色，则继续递归染色下一个节点；如果不能染上该颜色，则回溯到上一个节点，继续尝试其它颜色。如果所有颜色都尝试了，但都不能满足条件，则回溯到上一个节点，继续尝试其它颜色。如果所有节点都染色完毕，则说明染色成功，返回true；如果无解，则返回false。