2009年7月13日 星期一

题目链接：PKU 2492 A Bug's Life

分类：并查集的拓展

题目分析与算法模型 
         其实可以用pku 1182食物链那题的思路做，也使得其合并成一个并查集，记录与根节点的偏移量（0表示同一性别，1表示不同性别），当然合并两棵树的时候根于根节点之间的偏移量的公式需要自己推导一下，呵呵

Code:

 1#include<stdio.h>
 2#define max 2005
 3
 4int n,k,i,j,parent[max],kind[max],a,b,num,p,q,ccase=1;
 5bool f;
 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)
24{
25    int root1=find(x),root2=find(y);
26    if(root1==root2)
27    {
28        if(kind[x]==kind[y])f=true;
29    }
30    else
31    {
32        parent[root2]+=parent[root1];
33        parent[root1]=root2;
34        kind[root1]=(kind[y]+kind[x]+1)%2;
35    }
36}
37int main()
38{
39    scanf("%d",&num);
40    for(i=0;i<num;i++)
41    {
42        f=false;
43        scanf("%d%d",&p,&q);
44        init(p);
45        for(j=0;j<q;j++)
46        {
47            scanf("%d%d",&a,&b);
48            if(!f)Union(a,b);
49        }
50        printf("Scenario #%d:\n",ccase++);
51        if(f)printf("Suspicious bugs found!\n");
52        else printf("No suspicious bugs found!\n");
53        printf("\n");
54    }
55    return 0;
56}
57
58