hdu3635 Dragon Balls(带权并查集)-白红宇

题意：有N个城市，每一个城市都有一个龙珠（编号与城市的编号相同），有两个操作

T A ,B 将标号为A龙珠所在城市的所有的龙珠移动到B龙珠所在城市中！

思路：并查集（压缩路径的时候将龙珠移动的次数进行更新）

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define M 10005

using namespace std;

int f[M];//表示龙珠 i 所在的城市标号

int Tcnt[M];//记录每个龙珠移动的次数

int Scnt[M];//记录每个城市中龙珠总个数

int getFather(int x){

if(x==f[x])

return x;

int ff=getFather(f[x]);

Tcnt[x]+=Tcnt[f[x]];//每一个龙珠移动的次数+=其依附的父亲龙珠移动的次数

f[x]=ff;

return f[x];

}

void Union(int a, int b){

int fa=getFather(a);

int fb=getFather(b);

if(fa==fb) return;

f[fa]=fb;

Scnt[fb]+=Scnt[fa];//将fa城市的龙珠全部移动到fb城市中！

Scnt[fa]=0;

Tcnt[fa]+=1;//a球移动次数+1

}

int main(){

int t, a, b;

int n, m;

char ch[2];

scanf("%d", &t);

for(int cc=1; cc<=t; ++cc){

printf("Case %d:\n", cc);

scanf("%d%d", &n, &m);

memset(Tcnt, 0, sizeof(int)*(n+1));

for(int i=1; i<=n; ++i)

f[i]=i, Scnt[i]=1;

while(m--){

scanf("%s", ch);

if(ch[0]=='T'){

scanf("%d%d", &a, &b);

Union(a, b);

}

else {

scanf("%d", &a);

int ff = getFather(a);

printf("%d %d %d\n", ff, Scnt[ff], Tcnt[a]);

}

return 0;

}

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3902119.html，如需转载请自行联系原作者