L2-023 图着色问题 (25 分)

题目详情 - L2-023 图着色问题 (25 分) (pintia.cn)

思路：题意是判断是否为k染色的解，所以用set存颜色，不等k时就一定不是解，然后轮询每个点的相邻点是否颜色相同即可

#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int N = 510; 
vector<vector<int>> g(N);
int color[N];

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    while(m--){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int q;
    cin>>q;
    while(q--){
        set<int> s;
        for(int i = 1; i <= n; i++){
            cin>>color[i];
            s.insert(color[i]);
        }
        
        if(s.size() != k) {
            puts("No");
            continue;
        }
        
        bool flag = true;
        for(int i = 1; i <= n; i++) {
			for(int num:g[i])
                if(color[num] == color[i]){
                    flag = false;
                    break;
                }
		}
		
		if(flag) puts("Yes");
        else puts("No");
        
    }
    
    return 0;
}