原题传送:http://poj.org/problem?id=1988
一开始的想法是把下堆连到上堆去(这很符合树的结构思想),然后另外开一个数组标记录节点的值,递归的时候字节点加上这个标记的值与根节点的差值,但是发现,这样做在某些union_set时会使同一个根的所有节点标记的值错乱。
这道题需要对并查集有比较深刻的理解,多开一个数组记录堆总数。把上堆union到下堆上去,这样,总的根就是下堆的根,最上堆总是在最下层,find_set的时候就很方便求出答案。
View Code
1 #include <stdio.h> 2 #define N 30001 3 4 int a[N], f[N], num[N], v[N]; 5 6 int find_set(int x) 7 { 8 if(x != f[x]) 9 { 10 int tmp = f[x]; 11 f[x] = find_set(f[x]); 12 num[x] += num[tmp]; 13 } 14 return f[x]; 15 } 16 17 void union_set(int a, int b) 18 { 19 int x = find_set(a); 20 int y = find_set(b); 21 if(x != y) 22 { 23 f[x] = y; 24 num[x] += v[y]; 25 v[y] += v[x]; 26 } 27 } 28 29 void make_set() 30 { 31 for(int i = 0; i < N; i ++) 32 f[i] = i, num[i] = 0, v[i] = 1; 33 } 34 35 int main() 36 { 37 int p, a, b; 38 char op[5]; 39 make_set(); 40 scanf("%d", &p); 41 while(p --) 42 { 43 scanf("%s", op); 44 if(op[0] == 'M') 45 { 46 scanf("%d%d", &a, &b); 47 union_set(a, b); 48 } 49 else 50 { 51 scanf("%d", &a); 52 find_set(a); 53 printf("%d\n", num[a]); 54 } 55 } 56 return 0; 57 }