PTA | 程序设计类实验辅助教学平台

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？

但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入格式：

输入在第一行给出3个整数V（0

输出格式：

对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。

输入样例：

6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4

输出样例：

Yes
Yes
No
No

分析：

 这个题一开始想的是用并查集，后来发现不行；

只能老老实实建图了，这个就是建图后，遍历一遍，判断相邻的边颜色是否相同，还要判断所用的颜色数量是否和题给的一样就行了，不能多也不能少。

对于测试点五，题中给出的顶点最多是500个，边数最多也就是124750条，数组记得开大点，我就是数组开小了。

结论就是：图的问题，数据长度不要只看顶点，要考虑边的数量。

然后这个颜色数量，我们用一个set集合处理，set可以自动去重，然后看一下这个大小是否和题给大小一样就行了，每次使用记得清空。

链式前向星的话看这里——深度优先搜索(DFS) --- 提高篇_是饿梦啊的博客-CSDN博客

#include
#include
#include
#include
#include
#define x first
#define y secondusing namespace std;typedef long long LL;
typedef pair PII;const int N = 1000010;int v,t,k,n;int h[N],e[N],ne[N],idx;int a[N];
set st;void add(int a,int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx ++;
}int main()
{scanf("%d%d%d",&v,&t,&k);memset(h,-1,sizeof h);for(int i = 0 ;i < t ; i ++){int a,b;scanf("%d%d",&a,&b);add(a,b);add(b,a); }scanf("%d",&n);for(int i = 0 ; i < n ; i++){int flag = true;int cnt = 0;st.clear();	for(int j =1 ;j <= v ; j ++) scanf("%d",&a[j]),st.insert(a[j]);if(st.size()!= k){puts("No");continue;}for(int j = 1 ; j <= v ;j ++){	for(int k = h[j] ; k != -1 ;k = ne[k]){int c = e[k];if(a[j] == a[c]){puts("No");flag = false;break;}	}if(!flag) break;}if(flag)puts("Yes"); }return 0;
}