我叫张小黑
张小黑的挣扎生活
posts - 66,  comments - 109,  trackbacks - 0
pku 1988 cube stacking
 1#include<iostream>
 2#define MaxN 30000
 3typedef struct node{
 4    int count;
 5    int parent;
 6    int d;
 7}NODE;
 8NODE S[MaxN+1];
 9void init()
10{
11    for(int i=1;i<=MaxN;i++){
12        S[i].count=1;
13        S[i].d=0;
14        S[i].parent=i;}
15}
16int find_set(int x)
17{
18    int t=S[x].parent;
19    if(S[x].parent!=x){
20        S[x].parent=find_set(S[x].parent);
21        S[x].d+=S[t].d;
22    }
23    return S[x].parent;
24}
25void union_set(int x,int y)
26{
27    x=find_set(x);
28    y=find_set(y);
29    S[y].parent=x;
30    S[y].d=S[x].count;
31    S[x].count+=S[y].count;
32}
33int main()
34{
35    int P,x,y;
36    char c;
37    init();
38    scanf("%d",&P);
39    getchar();
40    while(P>0){
41        P--;
42        c=getchar();
43        if(c=='M'){
44            scanf("%d%d",&x,&y);
45            union_set(x,y);
46        }
47        else {
48            scanf("%d",&x);
49            y=find_set(x);
50            printf("%d\n",S[y].count-S[x].d-1);
51        }
52        getchar();
53    }
54    return 0;
55}
http://acm.pku.edu.cn/JudgeOnline/problem?id=1988
posted on 2008-01-27 22:48 zoyi 阅读(373) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


欢迎光临 我的白菜菜园

<2008年1月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(8)

随笔分类

随笔档案

文章档案

相册

acmer

online judge

队友

技术

朋友

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Copyright ©2024 zoyi Powered By博客园 模板提供：沪江博客