PTA 团体天梯赛L2-023
传送门

思路：
// 思路：图的遍历，建图后bfs搜索一下，注意：图中各点不保证一定连通，可能存在多个连通分量，
// 所以遍历时要将所有没有遍历到的点作为bfs初始点遍历一下
// 另外最后不同颜色的数量 保证：cnt == k,否则 puts(“No”);

AC代码：

#include <bits/stdc++.h>
#include <string.h>
#include <map>
#include <stack>
#include <queue>
#include <unordered_set>
using namespace std;
typedef long long LL;
typedef pair<int,int > PII;
const int INF=0x3f3f3f3f;
const int N=5e2+10;
const int M=5e5+10;
int T,n,m,k;
int head[N],e[M],ne[M],w[M],tot;
int st[N],color[N],cnt;
    int q[M];
bool used[N];
void add(int a,int b,int c){
    e[tot]=b,w[tot]=c,ne[tot]=head[a],head[a]=tot++;
}
bool bfs(int u){
    int hh=0,tt=0;
    q[tt++]=u;
    used[u]=1;
    while(hh < tt){
        int temp=q[hh++];
        if(!st[color[temp]]) cnt++,st[color[temp]]=1;
        if(cnt > k) return false; 
        for(int i=head[temp] ; i!=-1 ;i=ne[i]){
            int j=e[i];
            if(color[j] == color[temp]) return false;
            if(!used[j]){
                q[tt++]=j;
                used[j]=1;
            }
        }
    }
    return true;
}
// 思路：图的遍历，建图后bfs搜索一下，注意：图中各点不保证一定连通，可能存在多个连通分量，
// 所以遍历时要将所有没有遍历到的点作为bfs初始点遍历一下
// 另外最后不同颜色的数量 保证：cnt == k,否则 puts("No"); 
int main(){   
    memset(head , -1, sizeof head);
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b,0),add(b,a,0);
    }
    cin>>T;
    while(T--){
        bool flag=true;
        tot=cnt=0;
        memset(color , 0 ,sizeof color);
        memset(st , 0 ,sizeof st);
        memset(used , 0 , sizeof used);
        for(int i=1;i<=n;i++){
            scanf("%d",&color[i]);
        }
        for(int i=1;i<=n;i++){
            if(!used[i]) {
                if(!bfs(i)) flag=false;
            }
        }
        if(flag && cnt==k) puts("Yes");  
        else puts("No");
    }
    system("pause");
    return 0;
}