pku 1703

2009年7月13日 星期一

题目链接：PKU 1703 并查集的拓展 

分类：并查集的拓展

题目分析与算法模型
        类似于2492，算法基本一样，细节处稍作修改即可，呵呵


Code:

 1#include<stdio.h>
 2#define max 100005
 3
 4int i,j,parent[max],kind[max],t,n,m,a,b;
 5char kk;
 6
 7void init(int n)
 8{
 9    for(j=1;j<=n;j++)
10    {
11        parent[j]=-1;
12        kind[j]=0;
13    }
14}
15int find(int x)
16{
17    int t=parent[x];
18    if(t<0)return x;
19    parent[x]=find(t);
20    kind[x]=(kind[x]+kind[t])%2;
21    return parent[x];
22}
23void Union(int x,int y,char k)
24{
25    int root1=find(x),root2=find(y);
26    if(k=='A')
27    {
28        if(root1!=root2)printf("Not sure yet.\n");
29        else
30        {
31            if(kind[x]==kind[y])printf("In the same gang.\n");
32            else printf("In different gangs.\n");
33        }
34    }
35    else
36    {
37        if(root1!=root2)
38        {
39            parent[root2]+=parent[root1];
40            parent[root1]=root2;
41            kind[root1]=(kind[y]+kind[x]+1)%2;
42        }
43    }
44    
45}
46int main()
47{
48    scanf("%d",&t);
49    while(t--)
50    {
51        scanf("%d%d",&n,&m);
52        init(n);
53        for(i=0;i<m;i++)
54        {
55            scanf(" %c%d%d",&kk,&a,&b);
56            Union(a,b,kk);
57        }
58    }
59    return 0;
60}
61
62

posted on 2009-07-13 00:27 蜗牛也Coding 阅读(1071) 评论(2)  编辑 收藏 引用

评论

# re: pku 1703 2009-07-13 11:57 99读书人

不错！！  回复  更多评论   

# re: pku 1703[未登录] 2009-08-24 17:51 abilitytao

parent[root2]+=parent[root1];
这句有点多余 其实可以删掉  回复  更多评论   


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


<2010年9月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜