hdu 2818(带权并查集）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2818

思路：Count[i]表示i下面的积木个数，路径压缩的时候更新一下即可，sum[i]表示以i为根的积木的个数。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 30000+30
 7 int parent[MAXN];
 8 int sum[MAXN],Count[MAXN];
 9 int n;
10 
11 void Initiate() {
12     memset(Count,0,(MAXN)*sizeof(int));
13     for(int i=0; i<=MAXN; i++) {
14         parent[i]=i;
15         sum[i]=1;
16     }
17 }
18 
19 int Find(int x) {
20     if(x==parent[x])
21         return x;
22     int tmp=Find(parent[x]);
23     Count[x]+=Count[parent[x]];
24     return parent[x]=tmp;
25 }
26 
27 void Union(int u,int v) {
28     int r1=Find(u),r2=Find(v);
29     if(r1==r2)return ;
30     parent[r1]=r2;
31     Count[r1]=sum[r2];
32     sum[r2]+=sum[r1];
33 }
34 
35 int main() {
36     char str[2];
37     int u,v;
38 // freopen("1.txt","r",stdin);
39     scanf("%d",&n);
40     Initiate();
41     while(n--) {
42         scanf("%s",str);
43         if(str[0]=='M') {
44             scanf("%d%d",&u,&v);
45             Union(u,v);
46         } else {
47             scanf("%d",&u);
48             Find(u);
49             printf("%d\n",Count[u]);
50         }
51     }
52     return 0;
53 }

View Code