解题思路:这道题想了我好久,因为我把城市的编号一起考虑进去了,结果想了好久都没A,最后看了别人的题解居然都没有考虑到城市的编号,不考虑城市编号的问题的话就是一个很水的并查集了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=10000+10;
int parent[MAXN];
int _count[MAXN];
int Rank[MAXN];
int n,m;
void Initiate()
{
for(int i=1;i<=n;i++)
{
parent[i]=i;
_count[i]=0;
Rank[i]=1;
}
}
int Find(int x)
{
if(x==parent[x]) return x;
else
{
int tmp=parent[x];
parent[x]=Find(parent[x]);
_count[x]+=_count[tmp];//更新转移次数
}
return parent[x];
}
void Union(int R1,int R2)
{
int r1=Find(R1);
int r2=Find(R2);
if(r1==r2)return ;
else
{
parent[r1]=r2;
_count[r1]++;
Rank[r2]+=Rank[r1];
Rank[r1]=0;
}
}
int main()
{
int _case,t=1;
scanf("%d",&_case);
while(_case--)
{
scanf("%d%d",&n,&m);
Initiate();
printf("Case %d:\n",t++);
for(int i=1;i<=m;i++)
{
char str[11];
scanf("%s",str);
if(str[0]=='T')
{
int u,v;
scanf("%d%d",&u,&v);
Union(u,v);
}
else if(str[0]=='Q')
{
int x;
scanf("%d",&x);
int y=Find(x);
printf("%d %d %d\n",y,Rank[y],_count[x]);
}
}
}
return 0;
}