題目鏈接：http://poj.org/problem?id=1988
這道題當(dāng)指令是M的時(shí)候，就是并查集的合并工作了，C的時(shí)候自然就是查找，但是麻煩就是怎么去弄明白那個(gè)x下面到底有多少個(gè)元素，而且它是整列整列的弄的，所以需要找個(gè)東西標(biāo)記一下。
用一個(gè)域u標(biāo)記元素x的上面有多少個(gè)元素，用一個(gè)域d標(biāo)記元素x的下面有多少個(gè)元素，合并的時(shí)候只要更新這兩個(gè)域內(nèi)的值就行了，那么對(duì)于每一個(gè)查找指令，答案就是x所在集合根節(jié)點(diǎn)下面的元素個(gè)數(shù)減去元素x上面的元素個(gè)數(shù)再減去x本身咯～不過(guò)這個(gè)真心不好想啊～
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 30001
9 struct data
10 {
11 int p, u, d;
12 }p[N];
13 int find(int x)
14 {
15 int t;
16 if (p[x].p != x)
17 {
18 t = p[x].p;
19 p[x].p = find(t);
20 p[x].u += p[t].u;
21 }
22 return p[x].p;
23 }
24 int main()
25 {
26 int P;
27 int x, y;
28 int r1, r2;
29 char c;
30 for (int i = 1; i < N; i++)
31 {
32 p[i].p = i;
33 p[i].u = 0;
34 p[i].d = 1;
35 }
36 cin >> P;
37 while (P--)
38 {
39 scanf("\n%c", &c);
40 if (c == 'M')
41 {
42 scanf(" %d %d", &x, &y);
43 r1 = find(x); r2 = find(y);
44 if (r1 != r2)
45 {
46 p[r2].p = r1;
47 p[r2].u = p[r1].d;
48 p[r1].d += p[r2].d;
49 }
50 }
51 if (c == 'C')
52 {
53 scanf(" %d", &x);
54 y = find(x);
55 printf("%d\n", p[y].d - p[x].u - 1);
56 }
57 }
58 return 0;
59