poj2492

跟1703一样两种状态并查集+偏移量

两只虫子发射架关系判断有没有虫子是同性恋两两合并在一棵树上找右没有两个节点跟跟节点的关系（只有0,1两种）是相同的，相同就是gay

注意一点两组数据间有空行

View Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 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         else
26         {
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         else
63         printf("Suspicious bugs found!\n");
64         if(t!=0)
65         printf("\n");
66     }
67     return 0;
68 }