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

图的m着色问题可以使用回溯法进行求解。回溯法是一种基于深度优先搜索的算法，通过对问题的每一步进行穷举，直到找到问题的解。

下面是一个使用回溯法求解图的m着色问题的C++实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;

int n, m;
vector<int> G[MAXN];
int color[MAXN];

bool dfs(int u, int c) {
    color[u] = c;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (color[v] == c) return false;
        if (color[v] == 0 && !dfs(v, -c)) return false;
    }
    return true;
}

bool solve() {
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && !dfs(i, 1)) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if (solve()) {
        cout << "Yes" << endl;
        for (int i = 1; i <= n; i++) {
            cout << color[i] << " ";
        }
        cout << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

其中，`G`是图的邻接表表示，`color`表示每个节点的颜色（1或-1），`dfs`函数用于给每个节点染色，并判断是否合法，`solve`函数用于遍历每个节点并调用`dfs`函数进行染色，最后输出结果。

时间复杂度为O(2^n)，因为每个节点都有两种可能的颜色。实际上，由于在某些情况下可以提前剪枝，因此该算法的时间复杂度可能会更低。