数据结构 并查集

题目大意：

编号为1到N的球分别在N个城市中，有两种操作，T和Q，T表示把球A所在城市的所有球移动到球B所在城市。

Q表示输出球A所在城市的编号以及该城市中球的总数和球A被移动了多少次。

解题思路：由于每次移动球是将城市所有的球全部移动到另一个城市，因此可以用并查集来做，将两个集合合并，根节点

就表示球所在的城市。用根节点来记录球移动的次数和该城市的球的个数。

#include <iostream>
#include <cstdio>
#include <string.h>
#include <malloc.h>
using namespace std;
int t[10001],s[10001],v[10001];   //t[i]表示根节点移动次数，s[i]表示i城市的球的数目.
int find(int x)
{
while(x!=v[x])x=v[x];
return x;
}
void Union(int x,int y)
{
int m=find(x);int n=find(y);    //m,n分别表示x,y球所在的城市，然后将m合并到n 中。
if(m!=n)
{
  t[m]=1;
  v[m]=n;//合并到s[n]
  s[n]+=s[m];
  s[m]=0;//s[m]置0 
    }   //t[m]表示x球所在集合整体移动的次数。
}
void count(int x)
{
int sum=0;
while(x!=v[x])     //x球移动的次数也就是将根节点移动的次数相加。
{
sum+=t[x];
x=v[x];
}
printf("%d %d %d\n",x,s[x],sum);
}
int main()
{
int N;
cin>>N;
int k=0;
while(k++<N)
{
printf("Case %d:\n",k);
int m,n;
scanf("%d%d",&m,&n);
sizeof(t,0,sizeof(t));
for(int i=1;i<=m;i++)
{
v[i]=i;
s[i]=1;
}
while(n--)
{
char r;
scanf(" %c ",&r);
if(r==‘T‘)
{
int x,y;
scanf("%d%d",&x,&y);
Union(x,y);
}
else 
{
  int a;
  scanf("%d",&a);
  count(a);
}
}
}
return 0;
}

数据结构 并查集,布布扣,bubuko.com

数据结构 并查集

原文：http://blog.csdn.net/zzucsliang/article/details/22234735