2009年7月13日 星期一

題目鏈接：PKU 2492 A Bug's Life

分類：并查集的拓展

題目分析與算法模型 
         其實(shí)可以用pku 1182食物鏈那題的思路做，也使得其合并成一個(gè)并查集，記錄與根節(jié)點(diǎn)的偏移量（0表示同一性別，1表示不同性別），當(dāng)然合并兩棵樹的時(shí)候根于根節(jié)點(diǎn)之間的偏移量的公式需要自己推導(dǎo)一下，呵呵

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