hdu 2818 Building Block
Building Block
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3250 Accepted Submission(s): 973
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
题意：
1 /*有N个砖头， 编号1—N(实际上是0-N)，然后有两种操作，第一种是M x y 把x所在的那一堆砖头全部移动放到y所在的那堆上面。 第二种操作是 C x ，即查询x下面有多少个砖头 ，并且输出。 2 */
--->带权值的并查集
代码：
1 #include<cstring>
2 #include<cstdio>
3 #include<cstdlib>
4 #define maxn 30030
5 using namespace std;
6 int father[maxn];
7 __int64 rank[maxn],under[maxn];
8 int p;
9
10 void init(){
11
12 for(int i=0;i<maxn ;i++) {
13 father[i]=i;
14 rank[i]=1;
15 under[i]=0;
16 }
17
18 }
19
20 int fin(int x){
21
22 if(x == father[x])
23 return father[x];
24 int tem = father[x] ;
25 father[x] = fin(father[x]);
26 under[x]+=under[tem];
27
28 return father[x];
29
30 }
31
32 void Union(int a,int b){
33
34 int x = fin(a);
35 int y = fin(b);
36 if( x==y ) return ;
37 father[x] = y ; //将a所在的堆放在b的堆上
38 under[x] = rank[y];
39 rank[y] += rank[x];
40 rank[x] = 0;
41
42 }
43
44 int main()
45 {
46 char str[2];
47 int a,b;
48
49 while(scanf("%d",&p)!=EOF){
50 init();
51 while(p--){
52 scanf("%s",str);
53 if(str[0]=='M'){
54 scanf("%d%d",&a,&b);
55 Union(a,b);
56 }
57 else{
58 scanf("%d",&a);
59 fin(a);
60 printf("%I64d\n",under[a]);
61 }
62
63 }
64
65 }
66 return 0;
67 }