Description
Input
Output
Sample Input
2 3 3 T 1 2 T 3 2 Q 2 3 4 T 1 2 Q 1 T 1 3 Q 1
Sample Output
Case 1: 2 3 0 Case 2: 2 2 1 3 3 2有n个龙珠，在1到n个城市中，T a b 移动a所在城市的所有龙珠到b所在的城市，Q a 输出a所在的城市，城市的龙珠数量，a移动的次数，并查集问题，一个数组记录每个龙珠移动的次数，一个记录城市龙珠的数量，T a b 代表a移动的次数+1，并且所有指向a所在的城市的龙珠移动次数+1 ， b所在的城市龙珠数量加a所在的城市
#include <cstdio>
#include <cstring>
int p[11000] , c[11000] , num[11000] ;
/*int f(int x)
{
int r , k , l , temp = 0 ;
r = x ;
while( r != p[r] )
{
r = p[r] ;
temp++ ;
}
k = x ;
while( k != r )
{
l = p[k] ;
c[k] += ( --temp ) ;
p[k] = r ;
k = l ;
}
return r ;
}*/
int f(int x)
{
if(x==p[x])
return x;
int t=p[x];
p[x] = f(p[x]);
c[x] += c[t];
return p[x];
}
void add(int u,int v)
{
u = f(u) ;
v = f(v) ;
if(u != v)
{
p[u] = v ;
num[v] += num[u] ;
num[u] = 0 ;
c[u]++ ;
}
}
int main()
{
int t , tt , i , n , m , a , b ;
char ch ;
scanf("%d", &t);
for(tt = 1 ; tt <= t ; tt++)
{
printf("Case %d:\n", tt);
scanf("%d %d", &n, &m);
for(i = 1 ; i <= n ; i++)
{
p[i] = i ;
num[i] = 1 ;
}
memset(c,0,sizeof(c));
while(m--)
{
scanf("%*c%c", &ch);
if( ch == 'T' )
{
scanf("%d %d", &a, &b);
add(a,b);
}
else
{
scanf("%d", &a);
int k = f(a) ;
printf("%d %d %d\n", k, num[k] , c[a] );
}
}
}
return 0;
}
测试赛F - Dragon Balls(并查集),布布扣,bubuko.com
原文：http://blog.csdn.net/winddreams/article/details/38300599