图着色问题贪心算法c++

由于题目中没有给出具体的图着色问题，这里以经典的“地图着色”问题为例，给出一个贪心算法的C++实现。

地图着色问题是指在给定一张地图，要求对地图上的每个区域进行着色，使得相邻的区域颜色不同。这里假设地图中有N个区域，每个区域可以被着色成K种不同的颜色。

贪心算法的思想是，每次选择一个未被着色的区域，给它着上一个颜色，使得它与已经着色的区域不冲突。为了尽量减少颜色的使用，优先选择与当前区域相邻的已经着色的区域中使用最少的颜色。

具体实现如下：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 1005;

int n, k;
vector<int> g[MAXN]; // 图
int color[MAXN]; // 每个区域的颜色

// 判断颜色c是否与相邻的区域颜色冲突
bool check(int u, int c) {
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (color[v] == c) return false;
    }
    return true;
}

// 给区域u着色
void paint(int u) {
    int c = 1;
    while (!check(u, c)) c++; // 找到一个没有冲突的颜色
    color[u] = c;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;
        while (m--) {
            int j;
            cin >> j;
            g[i].push_back(j);
        }
    }
    memset(color, 0, sizeof(color));
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0) paint(i); // 如果这个区域没有被着色，就给它着色
    }
    for (int i = 1; i <= n; i++) {
        cout << color[i] << " ";
    }
    cout << endl;
    return 0;
}

该算法的时间复杂度为O(N*K*M)，其中N是区域的数量，K是颜色的数量，M是相邻区域的最大数量。在实际应用中，M通常不会太大，因此该算法的时间复杂度可以接受。