above[i]记录i方块之上的方块数
rank[i]记录树上总节点数(根节点)
M x y时把y所在树加到x所在树后，原x所在树的节点的above大小得更新，由于有路经压缩...具体看程序吧
1
#include<iostream>
2using namespace std;
3#define MAXN 30000
4#define MAXP 100000
5
6int parent[MAXN+1];
7int rank[MAXN+1]; //该数的结点(方块)数
8int above[MAXN+1]; //记录该方块之上有的方块数
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 阅读(182)
评论(0) 编辑 收藏 引用 所属分类:
POJ