PAT A1154 Vertex Coloring (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
/* 题意：图染色，任意相邻的两个顶点染色不能相同 给出一个图，问是否满足所有边的两个顶点颜色是否相同 思路：首先用用结构体存储每条边的信息，遍历图的每条边， 判断它的两个顶点颜色是否相同，若相同，则输出No，若遍历完后 每条边的两个顶点都不相同，则输出颜色的数量。由于要存储颜色的 数量，故可以使用set来保存每个顶点的颜色。最终set.size()则为 颜色的中总数。 注意： */
using namespace std;
const int N=1e4+10;
struct Node{
	int l,r;//边的两个顶点 
}node[N]; 

int main(){
	int n,m,k;
	cin>>n>>m;
	for(int i=0,l,r;i<m;i++){
		cin>>l>>r;
		node[i]={l,r};
	}
	cin>>k;
	int colors[N];//colors[i]表示点i的颜色 
	set<int> st;
	for(int i=0;i<k;i++){
		st.clear();
		//读入染色方案 
		for(int j=0,color;j<n;j++){
			cin>>color;
			colors[j]=color;
			st.insert(color); 
		}
		//判断输出结果
		bool flag=false;//flag==true表示该染色方案不合适 
		for(int t=0;t<m;t++){
			if(colors[node[t].l]==colors[node[t].r]){
				flag=true;
				break;
			}
		} 
		if(flag){
			printf("No\n");
		}else{
			printf("%d-coloring\n",st.size());
		}
	}
	return 0;
}