1
#include<iostream>
2using namespace std;
3#define MAXN 2000
4#define string1 "Scenario #"
5#define string2 "Suspicious bugs found!"
6#define string3 "No suspicious bugs found!"
7
8int parent[MAXN+1];
9int rank[MAXN+1];
10int dif[MAXN+1];
11
12void Init(int n=MAXN)
13
{
14
int i;
15 for(i=0;i<=n;i++)
16
{
17 rank[i]=0;
18 parent[i]=i;
19 dif[i]=-1;
20
}
21
}
22
23int find(int x)
24{
25
26 if(parent[x]!=x)
27 parent[x]=find(parent[x]);
28 return parent[x];
29}
30
31int merge_set(int a,int b)
32{
33 if(a==-1) return b;
34 if(b==-1) return a;
35 if(rank[a]>rank[b])
36 {
37 parent[b]=a;
38 return a;
39 }else{
40 parent[a]=b;
41 if(rank[a]==rank[b])
42 rank[b]++;
43 return b;
44 }
45}
46void Union(int a,int b)
47{
48 int root1=find(a),
49 root2=find(b),
50 da=merge_set(dif[root1],root2), //b的新根
51 db=merge_set(root1,dif[root2]); //a的新根
52 dif[db]=da;
53 dif[da]=db;
54}
55
56
57int main()
58{
59 int S,N,M,a,b,i;
60 bool flag;
61
62 scanf("%d",&S);
63 for(i=1;i<=S;i++)
64 {
65 scanf("%d%d",&N,&M);
66 Init(N);
67 flag=true;
68 while(M--)
69 {
70 scanf("%d%d",&a,&b);
71 Union(a,b);
72 if(find(a)==find(b)) flag=false;
73 }
74 if(flag==false)
75 printf("%s%d:\n%s\n\n",string1,i,string2);
76 else printf("%s%d:\n%s\n\n",string1,i,string3);
77
78 }
79 return 0;
80}
81
posted on 2009-04-21 16:42
wyiu 阅读(148)
评论(0) 编辑 收藏 引用 所属分类:
POJ