题解 | #小C的周末#

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;


inline int read(){
    int x=0,w=1;char ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w = -1;
    while(ch>='0' && ch<='9') x = x*10 + ch-'0', ch = getchar();
    return x*w;
}
int N,M,Q; 
int fa[100010]; //父系数组，用于表示各玩家之间的联系 
//离散化统计父系数组fa所代表集合中每个游戏的参与人数的个数个数，
//即fa[i]中的关系网中，各游戏所参与的人数 mp[i][游戏种类]=？,该“？”表示当前关系网中的当前游戏种类所包含的人数。 
map<int,int> mp[100010];
int ans[100010],cnt[100010];//ans答案保存处，cnt各种类游戏人数 

int find(int x){
	return (fa[x]==x ? x : fa[x]=find(fa[x]));
} 

int main(){
	
	while(~scanf("%d%d%d",&N,&M,&Q) ){
		
		//多组案例，1.容器内容的清除或初始化
		for(int i=1;i<=N;i++){
			mp[i].clear();
			fa[i]=i;//父系数组的重置，关系网的清除 
		} 
		memset(cnt,0,sizeof(cnt));
		memset(ans,-1,sizeof(ans));//数组初识化。
		//每个人想玩游戏，信息填入，统计
		int x;
		for(int i=1;i<=N;i++){
			scanf("%d",&x);
			mp[i][x]++;// i 集群的 x 游戏人数加一
			cnt[x]++; 
		} 
		//网线的接入，关系网的形成，集群中各游戏人数的更新。(mp是与fa相关联的）
		int u,v;
		for(int i=1;i<=Q;i++){
			
			scanf("%d%d",&u,&v);
			u=find(u),v=find(v);//找到属于自己的集群
			//小集群融入大集群
			if(mp[u].size()<mp[v].size()) swap(u,v);//以游戏种类划分？ 
			fa[v]=u;//小集群的父系 指向 大集群 
			
			//更新大集群的数据，即把小集群添加到大集群中 
			for(auto j:mp[v] ){
				mp[u][j.first]+=j.second;//当前游戏种类j.first的人数相加，mp[x][j.first]+mp[v][j.first] 
				//ans答案的统计
				if(mp[u][j.first]==cnt[j.first]&&ans[j.first]==-1)
				ans[j.first]=i;//当前添加网线的编号 
			} 
			mp[v].clear();//清除小集群 
		} 
		for(int i=1;i<=M;i++){
			if(cnt[i]==1) printf("0\n");
			else if (cnt[i]==0) printf("-1\n");
			else printf("%d\n",ans[i]);
		}

	}
	
	return 0;
}