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，如需轉載請自行聯系原作者