1 /* 2 目大意：输入一个数t，表示测试组数。然后每组第一行两个数字n,m，n表示有n只昆虫，编号从1—n,m表示下面要输入m行交配情况，每行两个整数，表示这两个编号的昆虫为异性，要交配。 3 要求统计交配过程中是否出现冲突，即是否有两个同性的昆虫发生交配。 4  5 思路：并查集 6    将同性的昆虫放入集合之中，如果输入的昆虫u, v同时出现在了集合中，那么 u，v就是同性的！发生了同性交配的可能！ 7 */ 8  9 #include <string>10 #include <cstdio>11 #include <cstring>12 #include <iostream>13 14 15 16 using namespace std;17 int n, m;18 int f[2010];19 int  mark[2010];//mark[i]表示 与 i 交配的昆虫的编号！20 21 int getFather(int x){22    return x==f[x] ? x : f[x]=getFather(f[x]);23 }24 25 void Union(int a, int b){26     int fa=getFather(a), fb=getFather(b);27     if(fa!=fb)28        f[fa]=fb;29 }30 31 int main(){32    int t, cnt=0;33    scanf("%d", &t);34    while(t--){35       36           scanf("%d%d", &n, &m);37           for(int i=1; i<=n; ++i)38           f[i]=i;39       memset(mark, 0, sizeof(mark));40       int flag=1;41       while(m--){42              int u, v;43          scanf("%d%d", &u, &v);44          if(flag){45             if(getFather(u) == getFather(v)){46                flag=0;47                            continue;48              }   49                         if(!mark[u] && !mark[v]){50                    mark[u]=v;51                    mark[v]=u;52                  }53                 else if(!mark[u]){54                    mark[u]=v;55                    Union(u, mark[v]); //如果v配对了，u没有配对，那么u和mark[v]就是同性昆虫，放入集合之中56             }57                  else if(!mark[v]){58                    mark[v]=u;        59                    Union(v,mark[u]);//,,,,,,60                 }61                else{ 62                   Union(u, mark[v]);//如果之前u和v都已经配对，现在u和v进行配对， 那么u和mark[v]是同性， v和mark[u]是同性！63               Union(v, mark[u]);64                }65          }66       }67       printf("Scenario #%d:\n",++cnt);68         if (flag==1) 69             printf("No suspicious bugs found!\n");70         else71             printf("Suspicious bugs found!\n");72         printf("\n");73    }74 }