poj2492A Bug's Life

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=2010;
 4 int f[maxn],r[maxn];
 5 int n,m,a,b;
 6 int ok;
 7 void init()
 8 {
 9     for(int i=1;i<=n;i++)
10     {
11         f[i]=i;
12         r[i]=0;
13     }
14 }
15 
16 int gf(int x)
17 {
18     if(x!=f[x])
19     {
20         int t=f[x];
21         f[x]=gf(t);
22         r[x]=(r[t]+r[x])%2;
23     }
24     return f[x];
25 }
26 
27 void uni(int a,int b)
28 {
29     int pa=gf(a);
30     int pb=gf(b);
31     if(pa==pb)
32     {
33         if(r[a]==r[b]) ok=1;
34     }
35     else
36     {
37         f[pb]=pa;
38         r[pb]=(r[a]+1-r[b])%2;
39     }
40 
41 }
42 int main()
43 {
44     int t;
45     int cas=0;
46     scanf("%d",&t);
47     while(t--)
48     {
49         ok=0;
50         scanf("%d%d",&n,&m);
51          init();
52         while(m--)
53         {
54             scanf("%d%d",&a,&b);
55             uni(a,b);
56         }
57         printf("Scenario #%d:
",++cas);
58         if(ok) puts("Suspicious bugs found!
");  //输出看样例格式！！！空行！！！
59         else puts("No suspicious bugs found!
");
60     }
61 }