hdu 3635（并查集+路径压缩变形）

解题思路：这道题想了我好久，因为我把城市的编号一起考虑进去了，结果想了好久都没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;
}