poj 2492 && 1703

题意：给出一些虫子，然后给出一些关系，每行的两个数 x y 表示 x 和 y 可以交配，问你是否可以在里面找出同性恋

思路：利用并查集记录他们的祖先，需要再用一个数组保存他们属于的种类，1代表一个类，0代表另一个类，在递归找祖先时同时给他们分类。然后询问的时候看他们是不是一个祖先，如果是一个祖先然后看他们是不是同一类，如果是证明他俩是同性恋；如果他们的祖先不相同，那么就要进行合并操作，同时修改一个祖先的类

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <string>
 6 #include <sstream>
 7 #include <map>
 8 #define N 2010
 9 #define M 10010
10 #define _clr(a,val) (memset(a,val,sizeof(a)))
11 
12 using namespace std;
13 
14 int f[N];
15 int a[N];
16 int find(int x)
17 {
18     int tem = f[x];
19     if(x != f[x])
20     f[x] = find(f[x]);
21     a[x] = (a[x] + a[tem]) % 2;  // 标记出他所属的类，他的类取决于他自身和他父亲所属的类
22     return f[x];
23 }
24 int main()
25 {
26     int t;
27     int cs = 0;
28     int i,n,m;
29     int x,y;
30     //freopen("data.txt","r",stdin);
31     scanf("%d",&t);
32     while(t--)
33     {
34         scanf("%d%d",&n,&m);
35         for(i = 0; i <= n; i++)
36         {
37             f[i] = i;
38             a[i] = 0;
39         }
40         int flag = 0;
41         for(i = 0; i < m; i++)
42         {
43             scanf("%d%d",&x,&y);
44             if(flag) continue;
45             int root1 = find(x);
46             int root2 = find(y);
47             if(root1 == root2)
48             {
49                 if(a[x] % 2 == a[y] % 2)
50                 {
51                     flag = 1;
52                 }
53             }
54             else
55             {
56                 f[root1] = root2; // 合并
57                 a[root1] = (a[y] - a[x] + 1) % 2;  // 修改一个祖先的类
58             }
59         }
60         printf("Scenario #%d:\n",++cs);
61         if(flag) cout<<"Suspicious bugs found!\n";
62         else cout<<"No suspicious bugs found!\n";
63         if(t) cout<<endl;
64     }
65     return 0;
66 }

题目：http://poj.org/problem?id=1703

题意：给两种操作：D A B 说明 A B不在一间屋子里，A A B 询问 A B 是否在一个屋子里，还是不能确定A B的关系

思路：跟上一个题一样的思想，如果是 D 则进行合并操作，如果A则判断，具体看代码吧

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #define N 100010
 6 #define _clr(a,val) (memset(a,val,sizeof(a)))
 7 
 8 using namespace std;
 9 
10 int f[N];
11 int mark[N];
12 int find(int x)
13 {
14     int tem = f[x];
15     if(x != f[x])
16     f[x] = find(f[x]);
17     mark[x] = (mark[x] + mark[tem]) % 2;
18     return f[x];
19 }
20 int main()
21 {
22     int t,i;
23     int n,m;
24     char ch[10];
25     int x,y;
26     //freopen("data.txt","r",stdin);
27     scanf("%d",&t);
28     while(t--)
29     {
30         for(i = 0; i < n; i++)
31         scanf("%d%d",&n,&m);
32         for(i = 1; i <= n; i++)
33         {
34             f[i] = i;
35             mark[i] = 0;
36         }
37         for(int i = 0;i < m; i++)
38         {
39             scanf("%s%d%d",&ch,&x,&y);
40             int root1 = find(x);
41             int root2 = find(y); 
42             if(ch[0] == 'D')  // 如果是D则直接合并
43             {
44                 f[root2] = root1;
45                 mark[root2] = (mark[x] - mark[y] + 1) % 2; // 修改类
46             }
47             else // 如果是A 则判断
48             {
49                 if(root1 != root2)  // 如果根不同，则无法判断关系
50                 printf("Not sure yet.\n");
51                 else if(mark[x] == mark[y])  // 如果所属类相同，则是一个房间
52                 printf("In the same gang.\n");
53                 else printf("In different gangs.\n");
54             }
55         }
56     }
57     return 0;
58 }