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

图的m着色问题可以采用回溯法来解决，具体步骤如下：

1. 定义一个数组color，用来存储每个节点的颜色。

2. 从图的任意一个节点开始，对其进行染色，然后对该节点的所有相邻节点进行遍历，如果相邻节点还未染色，则对其进行染色，否则继续遍历其他相邻节点。

3. 如果在遍历过程中发现某个节点不能被染成当前颜色，就回溯到上一个节点，重新选择颜色进行染色。

4. 重复步骤2和3，直到所有节点都被染色或者无法再继续染色为止。

下面是一个C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1000; // 最大节点数
int color[MAXN]; // 存储每个节点的颜色
vector<int> graph[MAXN]; // 图的邻接表表示

bool is_valid(int v, int c) { // 判断节点是否可以染成颜色c
    for (int i = 0; i < graph[v].size(); i++) {
        int u = graph[v][i];
        if (color[u] == c) return false;
    }
    return true;
}

bool backtrack(int v, int m) { // 回溯法求解
    if (v == MAXN) return true; // 所有节点都染色完毕，返回true
    for (int c = 1; c <= m; c++) {
        if (is_valid(v, c)) {
            color[v] = c; // 染色
            if (backtrack(v + 1, m)) return true; // 继续向下染色
            color[v] = 0; // 回溯到上一个节点
        }
    }
    return false;
}

int main() {
    int n, m; // n表示节点数，m表示颜色数
    cin >> n >> m;
    for (int i = 0; i < n; i++) { // 输入图的邻接表表示
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    if (backtrack(0, m)) { // 求解
        cout << "Solution found:" << endl;
        for (int i = 0; i < n; i++) cout << color[i] << " ";
        cout << endl;
    }
    else cout << "No solution found." << endl;
    return 0;
}