above[i]記錄i方塊之上的方塊數(shù)
rank[i]記錄樹上總節(jié)點數(shù)(根節(jié)點)
M x y時把y所在樹加到x所在樹后，原x所在樹的節(jié)點的above大小得更新，由于有路經(jīng)壓縮...具體看程序吧
1
#include<iostream>
2using namespace std;
3#define MAXN 30000
4#define MAXP 100000
5
6int parent[MAXN+1];
7int rank[MAXN+1]; //該數(shù)的結(jié)點(方塊)數(shù)
8int above[MAXN+1]; //記錄該方塊之上有的方塊數(shù)
9
10void init(int n=MAXN)
11
{
12
int i=0;
13 for(i=1;i<=n;i++)
14
{
15 parent[i]=-1;
16 rank[i]=1;
17
}
18
}
19
20int find(int x)
21{
22 int p = x,temp,tp;
23 while( parent[p] > 0) p = parent[p];
24 while( x != p )
25 {
26 tp=temp = parent[x];
27 parent[x] = p;
28 while(temp!= p) //難理解的地方
29 {
30 above[x]+=above[temp];
31 temp=parent[temp];
32 }
33 x = tp;
34 }
35 return p;
36}
37
38void Union(int x,int y)
39{
40 int root1=find(x),
41 root2=find(y);
42 if(root1==root2) return ;
43 above[root2]=rank[root1];
44 rank[root1]+=rank[root2];
45 parent[root2]=root1;
46}
47
48int main()
49{
50 int P,x,y;
51 char c;
52 init();
53 scanf("%d",&P);
54 while(P--)
55 {
56 scanf(" %c",&c,&x,&y);
57 if(c=='M')
58 {
59 scanf("%d%d",&x,&y);
60 Union(x,y);
61 }else{
62 scanf("%d",&x);
63 y=find(x);
64 printf("%d\n",rank[y]-above[x]-1);
65 }
66 }
67 return 0;
68}
69
70
71
72
posted on 2009-04-23 20:57
wyiu 閱讀(183)
評論(0) 編輯 收藏 引用 所屬分類:
POJ