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