链接：https://www.nowcoder.com/acm/contest/50/G
来源：牛客网

题目描述

#include<bits/stdc++.h>
using namespace std;
const int maxn=200007;
int par[maxn],ran[maxn],id[maxn],ans;
void init()
{for(int i=0;i<maxn;i++)par[i]=i,ran[i]=1,id[i]=i;
}
int find(int x)
{if(x==par[x])return x;return par[x]=find(par[x]);
}
void unite(int x,int y)
{x=find(x);y=find(y);if(x!=y){par[x]=y;ran[y]+=ran[x];ran[x]=0;}
}
int main()
{int T,cas=0;scanf("%d",&T);while(T--){printf("Case #%d:\n",++cas);int n,m,cnt;scanf("%d%d",&n,&m);init();cnt=ans=n;cnt++;while(m--){char t[10];int x,y;scanf("%s",&t);if(t[0]=='q') printf("%d\n",ans);else if(t[0]=='f'){int x,y;scanf("%d%d",&x,&y);int x1=find(id[x]),y1=find(id[y]);if(x1==y1)continue;if(ran[x1]>ran[y1]){printf("%d is winner!\n",x);unite(x1,y1);ans--;}else if(ran[x1]<ran[y1]){printf("%d is winner!\n",y);unite(x1,y1);ans--;}else printf("Either is winner!\n");}else if(t[0]=='t'){int x,y;scanf("%d%d",&x,&y);x=find(id[x]);int y1=find(id[y]);if(ran[y1]==1)ans--;ran[y1]--;id[y]=cnt++;unite(x,id[y]);}else if(t[0]=='r'){int x;scanf("%d",&x);int x1=find(id[x]);if(ran[x1]>1)id[x]=cnt++,ran[x1]--,ans++;}}} return 0;
}