hdu 2818 Building Block (带权并查集，很优美的题目)

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

Sample Output

1 
0 
2

Source

2009 Multi-University Training Contest 1 - Host by TJU

题目大意：有N个piles（按序编号），每次有两种操作：

M x y表示把x所在的那一堆全部移到y所在的那一堆

C x 询问在x之下有多少个方块

解决方法：使用并查集（路径压缩）实现，然后用count[X]表示X所在的那一堆总共多少个piles，under[x]表示x之下有多少个piles。

首先，每次操作我们合并两个集合（如果原来在同一集合中除外），count[X]是每次操作可以直接实现的,就是把两堆的数目相加，很容易（初始值为1）。那么当某次移动操作发生时，首先确定x所在的那一堆最底部的X以及y所在那一堆最底部的Y，那么under[X]的数目就是另外一堆piles的总数count[Y]，有了这个条件，在接下去的操作中，就可以根据FIND（x）递归去一边寻找根一边更新其他未知的under[x]。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 30006
 6 int fa[N];
 7 int under[N];//下边的个数
 8 int cnt[N];//所在堆的堆个数
 9 void init(){
10     for(int i=0;i<N;i++){
11         fa[i]=i;
12         under[i]=0;
13         cnt[i]=1;
14     }
15 }
16 int find(int son){
17     if(fa[son]!=son){
18         int t=find(fa[son]);
19         under[son]+=under[fa[son]];
20         fa[son]=t;
21     }
22     return fa[son];
23     //return fa[x]==x?x:fa[x]=find(fa[x]);
24 }
25 void merge(int x,int y){
26     int root1=find(x);
27     int root2=find(y);
28     if(root1==root2)return;
29     under[root1]=cnt[root2];
30     cnt[root2]+=cnt[root1];
31     fa[root1]=root2;
32 }
33 int main()
34 {
35     int n;
36     while(scanf("%d",&n)==1){
37         init();
38         char s[3];
39         int x,y;
40         for(int i=0;i<n;i++){
41             scanf("%s",s);
42             if(s[0]=='M'){
43                 scanf("%d%d",&x,&y);
44                 merge(x,y);
45             }
46             else{
47                 scanf("%d",&x);
48                 find(x);
49                 printf("%d
",under[x]);
50             }
51         }
52     }
53     return 0;
54 }

View Code

Recommend