用C++写一个图的着色问题算法的代码

以下是一个简单的图的着色问题算法的 C++ 代码，它使用了贪心算法：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100;

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

bool is_safe(int node, int c) {
    for (int i = 0; i < graph[node].size(); i++) {
        int neighbor = graph[node][i];
        if (color[neighbor] == c) {
            return false;
        }
    }
    return true;
}

bool graph_coloring(int node) {
    if (node == n) {
        return true;
    }
    for (int c = 1; c <= m; c++) {
        if (is_safe(node, c)) {
            color[node] = c;
            if (graph_coloring(node + 1)) {
                return true;
            }
            color[node] = 0;
        }
    }
    return false;
}

int main() {
    // 输入 n 和 m
    cin >> n >> m;
    // 输入图的边
    int u, v;
    while (cin >> u >> v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    // 对每个节点进行着色
    if (graph_coloring(0)) {
        cout << "Graph can be colored with " << m << " colors:" << endl;
        for (int i = 0; i < n; i++) {
            cout << "Node " << i << " has color " << color[i] << endl;
        }
    } else {
        cout << "Graph cannot be colored with " << m << " colors!" << endl;
    }
    return 0;
}

在这个算法中，我们首先输入了图的节点数和颜色数，然后输入每条边。然后我们通过递归，尝试为每个节点着色。对于每个节点，我们尝试使用每种颜色进行着色，并检查是否满足“相邻节点不能有相同颜色”的条件。如果找到了一种着色方案，则返回 true，否则返回 false。最后，如果找到了一种方案，我们输出每个节点的颜色；否则，输出一个错误消息。