跟1703一样 两种状态 并查集+偏移量
两只虫子发射架关系 判断有没有虫子是同性恋 两两合并 在一棵树上找右没有两个节点跟跟节点的关系（只有0,1两种）是相同的，相同就是gay
注意一点 两组数据间有空行
View Code 1 #include2 #include 3 int father[2001],num[2001],r[2001]; 4 int find(int x) 5 { 6 if(x!=father[x]) 7 { 8 int y = father[x]; 9 father[x] = find(father[x]);10 num[x] = (num[x]+num[y])%2;11 }12 return father[x];13 }14 void union1(int x, int y)15 {16 int x1 = find(x);17 int y1 = find(y);18 if(x1!=y1)19 {20 if(r[x1]>r[y1])21 {22 father[y1] = x1;23 num[y1] = (num[x]-num[y]+1)%2;24 }25 else26 {27 father[x1] = y1;28 num[x1] = (num[y]-num[x]+1)%2;29 if(r[x1] == r[y1])30 r[y1]++;31 }32 }33 }34 int main()35 {36 int i, j, m, n,t,a,b,g;37 long k;38 scanf("%d", &t);39 while(t--)40 {41 k++;42 scanf("%d%d", &n, &m);43 int flag = 0;44 for(i = 1 ; i <= n ; i++)45 {46 father[i] = i;47 r[i] = 0;48 num[i] = 0;49 }50 j = 0;51 for(i = 1 ; i <= m ; i++)52 {53 scanf("%d%d", &a,&b);54 if(a!=b)55 union1(a,b);56 if(find(a) == find(b)&&num[a]==num[b])57 flag = 1;58 }59 printf("Scenario #%ld:\n",k);60 if(flag == 0)61 printf("No suspicious bugs found!\n");62 else63 printf("Suspicious bugs found!\n");64 if(t!=0)65 printf("\n");66 }67 return 0;68 }