地图着色问题c++

地图着色问题是一个经典的图论问题，其目标是用最少的颜色对一个无向图的节点进行染色，使得相邻的节点颜色不同。这个问题可以使用贪心算法来解决，具体步骤如下：

1. 对节点进行排序，按照节点的度数从大到小进行排序；
2. 从度数最大的节点开始，选择一个未被染色的颜色给它染色；
3. 对于该节点的相邻节点，如果还没有被染色，就选择一个未被染色的颜色给它染色；
4. 重复以上步骤，直到所有节点都被染色。

下面是一个使用 C++ 实现的地图着色算法的代码示例：

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

using namespace std;

int main() {
    int n, m; // n 表示节点数，m 表示边数
    cin >> n >> m;

    vector<int> degree(n); // 存储每个节点的度数
    vector<vector<int>> adj(n); // 存储每个节点的相邻节点

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> color(n, -1); // 存储每个节点的颜色，-1 表示未染色

    // 对每个节点的度数进行排序
    vector<pair<int, int>> deg(n);
    for (int i = 0; i < n; i++) {
        deg[i] = {degree[i], i};
    }
    sort(deg.rbegin(), deg.rend());

    // 对每个节点进行染色
    for (int i = 0; i < n; i++) {
        int u = deg[i].second;
        if (color[u] != -1) continue; // 如果已经染过色，就跳过
        vector<bool> used(n); // 标记已经使用的颜色
        for (int v : adj[u]) {
            if (color[v] != -1) {
                used[color[v]] = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (!used[j]) {
                color[u] = j;
                break;
            }
        }
    }

    // 输出每个节点的颜色
    for (int i = 0; i < n; i++) {
        cout << "Node " << i << " is colored " << color[i] << endl;
    }

    return 0;
}

上面的代码使用了 vector 存储节点的度数和相邻节点，还使用了 pair 存储节点的度数和编号，方便排序。在染色时，使用了一个 bool 数组来标记已经使用的颜色，如果某个颜色已经被染过了，就将对应的标记设置为 true。最后，输出每个节点的颜色即可。