题意:有n组人分别玩不同的游戏,现在按给定次序连接两个人的电脑,只有当这组所有的人都被连在一起时他们才可以开始游戏,问每一组人最早连接到第几条线可以开始游戏。

并查集嘛,看到分组,连接几个字就大概有方向了,但是问题在于普通的并查集默认所有的人都是一组,像这样多组的情况有点像食物链那道题,如果你做过那就很容易想到,其实说白了就是把普通并查集里的一个集合给扩展,现在我这一个集合不仅保存了连接起来的人,还保存了每个人的游戏组别,合并的时候只要把这些属性一起合并就好了

但是这题数据范围很大,开数组会爆,所以用以前学过的知识,我们用Map去存离散的数据就好了。

#include <bits/stdc++.h>
using namespace std;
//x[i][j]代表第i组中玩j号游戏的人数,
map<int,int>x[100001];
//记录第i组的父亲是谁
int fa[100001];
//cnt[i]代表第i组下有cnt[i]个人,按秩合并用的
int cnt[100001];
//num[i]代表总共有num[i]个人玩第i号游戏
int num[100001];
//答案要按照游戏的序号输出,所以我们存一下
int ans[100001];

void init(int n){
	for(int i=1;i<=n;i++){
		x[i].clear();
		fa[i]=i;
		cnt[i]=1;
		ans[i]=0;
		num[i]=0;
	}
}	

int find(int a){
	if(fa[a]==a){
		return a;
	}
	return fa[a]=find(fa[a]);
}

int main(){
	int n,k,m;
    //题目说有多组输入,我在这卡了半小时,无语了家人们
	while(cin>>n>>k>>m){
        //多组样例初始化肯定要的
		init(n);	
		for(int i=1;i<=n;i++){
			int t;
			cin>>t;
			num[t]++;
			x[i][t]++;
		}
		for(int i=0;i<m;i++){
			int a,b;
			cin>>a>>b;
			int A=find(a);
			int B=find(b);
			if(A==B){
				continue;
			}
            //这里如果不按秩合并,树会退化成链表,造成mle
			if(cnt[A]>cnt[B]){
				swap(A,B);
				swap(a,b);
			}
			if(A!=B){
				fa[A]=B;
				cnt[B]+=cnt[A];
				cnt[A]=0;
                //把A中的每个游戏的人数对应地加到B中
				for(auto it : x[A]){
					x[B][it.first]+=it.second;
					if(x[B][it.first]==num[it.first]){
						ans[it.first]=i+1;
					} 
				}	 
			}
		}
		for(int i=1;i<=k;i++){
            //如果这个游戏只有一个人玩,直接开始
			if(num[i]==1){
				cout<<0<<endl;
			}else if(ans[i]==0){//到死也玩不上,呜呜呜
				cout<<-1<<endl;
			}else{
				cout<<ans[i]<<endl;
			}		
		}
	}	
	return 0;
}