c++贪心算法图着色

以下是C++中使用贪心算法进行图着色的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m; // n表示节点数，m表示边数
    vector<vector<int>> graph(n); // 存储图的邻接表
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> colors(n, -1); // 存储每个节点的颜色，初始化为-1
    for (int i = 0; i < n; i++) {
        vector<bool> used(n, false); // 存储相邻节点已经使用的颜色
        for (int j = 0; j < graph[i].size(); j++) {
            int neighbor = graph[i][j];
            if (colors[neighbor] != -1) {
                used[colors[neighbor]] = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (!used[j]) {
                colors[i] = j;
                break;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << "Node " << i << " is colored with " << colors[i] << endl;
    }
    return 0;
}

该算法的基本思想是，对于每个节点，选择一个未被相邻节点使用的最小颜色进行着色。具体实现中，我们可以使用一个vector来存储每个节点的颜色，初始化为-1表示未着色。然后对于每个节点，遍历其相邻节点，记录已经使用的颜色，然后选择一个未被使用的最小颜色进行着色。