問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1988思路:
并查集的妙用
up[i]記錄節(jié)點i到根節(jié)點的距離(有多少元素)
sum[i]記錄以i作為根節(jié)點的樹所包含的節(jié)點的個數(shù)
重點是在進行union與find操作時如何更新這兩個數(shù)組，find操作所暗含路徑壓縮時up數(shù)組的更新較難理解
參考:
http://www.shnenglu.com/longzxr/archive/2009/07/13/89974.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_NUM 30005
5 int father[MAX_NUM], up[MAX_NUM], sum[MAX_NUM];
6
7 void
8 init()
9 {
10 int i;
11 for(i=1; i<MAX_NUM; i++) {
12 father[i] = i;
13 sum[i] = 1;
14 up[i] = 0;
15 }
16 }
17
18 int
19 find(int item)
20 {
21 int tmp = father[item];
22 if(father[item] != item) {
23 father[item] = find(father[item]);
24 up[item] += up[tmp];
25 }
26 return father[item];
27 }
28
29 void
30 uunion(int top, int down)
31 {
32 int a = find(top);
33 int b = find(down);
34 if(a == b)
35 return;
36 father[b] = a;
37 up[b] = sum[a];
38 sum[a] += sum[b];
39 }
40
41 int
42 main(int argc, char **argv)
43 {
44 int p, top, down, r, cube;
45 char ch[2];
46 scanf("%d", &p);
47 init();
48 while(p--) {
49 scanf("%s", ch);
50 if(ch[0] == 'M') {
51 scanf("%d %d", &top, &down);
52 uunion(top, down);
53 } else {
54 scanf("%d", &cube);
55 r = find(cube);
56 printf("%d\n", sum[r]-up[cube]-1);
57 }
58 }
59 }