poj2492_A Bug's Life_并查集

 1 #include <iostream>
 2 #include <cstdio>
 3 #define MAX_N 150000+5
 4 
 5 using namespace std;
 6 
 7 int par[MAX_N];//父节点
 8 int depth[MAX_N];//深度
 9 
10 void init(int n){
11    for(int i=0;i<=n;i++){
12        par[i]=i;
13        depth[i]=1;
14    }
15 }
16 int find_father(int t){
17    if(t==par[t]){
18        return t;
19    }else{
20        return par[t]=find_father(par[t]);
21        //实现了路径压缩
22    }
23 }
24 void unite(int t1,int t2){
25    int f1=find_father(t1);
26    int f2=find_father(t2);
27    if(f1==f2){
28        return ;
29    }
30    if(depth[f1]<depth[f2]){
31        par[f1]=f2;
32    }else{
33        par[f2]=f1;
34        if(depth[f1]==depth[f2]){
35            depth[f1]++;
36            //记录深度
37        }
38    }
39 }
40 
41 bool same(int x,int y){
42     return find_father(x)==find_father(y);
43 }
44 
45 int main()
46 {
47     int t;
48     int n,k;
49     int a,b;
50     bool ans=false;
51     scanf("%d",&t);
52     for(int kk=0;kk<t;kk++){
53         scanf("%d %d",&n,&k);
54         init(n*2);
55         ans=false;
56         for(int i=0;i<k;i++){
57             scanf("%d %d",&a,&b);
58             if(same(a,b)){
59                 ans=true;
60             }else{
61                 unite(a,b+n);
62                 unite(a+n,b);
63             }
64         }
65         printf("Scenario #%d:\n",kk+1);
66         if(ans){
67             printf("Suspicious bugs found!\n");
68         }else{
69             printf("No suspicious bugs found!\n");
70         }
71         printf("\n");
72 
73     }
74     return 0;
75 }