题意:有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; }