pku 1988

2009年7月13日 星期一

题目链接：PKU 1988  Cube Stacking

分类：并查集的应用

Code：

 1#include<stdio.h>
 2#define max 30005
 3int p,a,b,parent[max],up[max],sum[max];
 4char cc;
 5void init()
 6{
 7    int i;
 8    for(i=1;i<=max;i++)
 9    {
10        parent[i]=-1;
11        up[i]=0;  //up[i]记录从节点i到根节点之间有多少个元素(不包括i),                                               
12        sum[i]=1; //sum记录当前节点若为总的根节点时该树的元素总数
13    }
14}
15int find(int x)
16{
17    int t=parent[x];
18    if(t<0) return x;
19    parent[x]=find(parent[x]);
20    up[x]+=up[t];
21    return parent[x];
22}
23void Union(char c)
24{
25    if(c=='M')      //合并时将叠上面的方块栈所构成的树的根(root1)放上面,root1做根
26    {
27        int root1=find(a),root2=find(b);
28        parent[root1]+=parent[root2];
29        parent[root2]=root1;
30        up[root2]=sum[root1];
31        sum[root1]+=sum[root2];
32    }
33    else 
34    {
35        int t=find(a);
36        printf("%d\n",sum[t]-up[a]-1);
37    }
38}
39int main()
40{
41    scanf("%d",&p);
42    init();
43    while(p--)
44    {
45        scanf(" %c",&cc);
46        if(cc=='M')scanf("%d%d",&a,&b);
47        else scanf("%d",&a);
48        Union(cc);
49    }
50    return 0;
51}
52
53

posted on 2009-07-13 23:12 蜗牛也Coding 阅读(869) 评论(0)  编辑 收藏 引用


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


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜