HDU 1829 A Bug's Life

 1 #include <iostream>
 2 #include <cstdio> 
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 #define MAXN 5010
 9 
10 int pre[MAXN];
11 
12 void init(int n)
13 {
14     for(int i = 1; i <= 2*n; i++)
15     {
16         pre[i] = i;                                            
17     }
18 }
19 
20 int find(int x)
21 {
22     if(x != pre[x])
23         pre[x] = find(pre[x]);
24         
25     return pre[x];
26 }
27 
28 void merge(int x, int y)
29 {
30     int fx = find(x);
31     int fy = find(y);
32     if(fx != fy)
33     {
34         pre[fx] = fy;
35     }
36 }
37  
38 int main()
39 {
40     int t, n, m;               
41     scanf("%d", &t);
42     for(int k = 1; k <= t; k++)
43     {
44         scanf("%d%d", &n, &m);
45         init(n);  
46         int a, b;
47         int sum = 0;
48         for(int i = 1; i <= m; i++)
49         {
50             scanf("%d%d", &a, &b);
51             if((find(a) == find(b)) || (find(a+n) == find(b+n)))
52                 sum++;
53             else    
54             {
55                 merge(a, b+n);
56                 merge(a+n, b);
57             }            
58         }
59         printf("Scenario #%d:\n", k);
60         if(!sum)     
61             printf("No suspicious bugs found!\n\n");
62         else
63             printf("Suspicious bugs found!\n\n");
64     }
65     return 0;
66  }