HDU 2818 Building Block, poj 1988 Cube Stacking(带权并查集)

链接:

HDU: http://acm.hdu.edu.cn/showproblem.php?pid=2818

POJ:  http://poj.org/problem?id=1988

题目：

Problem Description John are playing with blocks. There are N blocks (1 <= N <= 30000) numbered 1...N。Initially, there are N piles, and each pile contains one block. Then John do some operations P times (1 <= P <= 1000000). There are two kinds of operation:

M X Y : Put the whole pile containing block X up to the pile containing Y. If X and Y are in the same pile, just ignore this command. 

C X : Count the number of blocks under block X 

You are request to find out the output for each C operation.

Input The first line contains integer P. Then P lines follow, each of which contain an operation describe above.  

Output Output the count for each C operations in one line.  

Sample Input

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
        

Sample Output

1
0
2
        

Source 2009 Multi-University Training Contest 1 - Host by TJU  

题目大意：

有N个砖头，编号为1～N，  然后有两种操作， 第一种是M  x  y,  把x所在的那一堆砖头全部移动放到y所在的那堆的上面。  第二种操作是C  x，  即查询x下面有多少个砖头，并且输出。

分析与总结：

带权并查集的应用， 用num数组来表示每一棵树的总数， rank[x]数组来表示x砖头下面有多少个砖头。

如果把a堆砖放到b堆砖上面， 那么a堆最底面那个砖头root_a的下面原本是有0个砖头的， 搬过去之后，变成了有b堆砖的数量个。然后root_a之上的数量便根据root_a的值进行更新。更新的步骤在查找时路径压缩的那一步进行。

代码：

#include<cstdio>

const int N = 30005;
int f[N];
long long rank[N],num[N];

inline void init(){
    for(int i=0; i<N; ++i)
        f[i]=i,rank[i]=0,num[i]=1;
}
int find(int x){
    if(x==f[x]) return f[x];
    int fa = f[x];
    f[x] = find(f[x]);
    if(rank[fa]!=0)
        rank[x] += rank[fa];
    return f[x];
}

inline void Union(int x,int y){
    int a=find(x), b=find(y);
    if(a==b) return ;
    rank[a] = num[b];
    f[a] = b;
    num[b] += num[a];
    num[a] = 0;
}

int main(){
    int t, x, y;
    char cmd[3];
    scanf("%d",&t);
    init();
    for(int i=0; i<t; ++i){
        scanf("%s",cmd);
        if(cmd[0]=='M'){
            scanf("%d%d",&x,&y);
            Union(x,y);
        }
        else{
            scanf("%d",&x);
            find(x);
            printf("%lld\n", rank[x]);
        }
    }
    return 0;
}
           

——  生命的意义，在于赋予它意义。

    
     
                
     
     
           原创 http://blog.csdn.net/shuangde800 ， By   D_Double  (转载请标明)