hdu

http://acm.hdu.edu.cn/showproblem.php?pid=1829

http://poj.org/problem?id=2492

臭虫有两种性别，并且只有异性相吸，给定n条臭虫（编号1-n）和m对关系，判断是否是出现同性恋的情况。

这题跟食物链的题类似，这里只有两种关系，关系是同性或者异性。

对于每只动物创建两个元素同性或异性，并用这 2×n个元素建立并查集。

首先判断输入的x和y是否是一个组的。是就flag=1.

然后，如果x和y是一对，那么合并x和y+n，x+n和y。

 1 #include <cstdio>
 2 const int maxn = 2010;
 3 int par[2*maxn];
 4 
 5 void init(int n)
 6 {
 7     for(int i=1;i<=n;i++)
 8         par[i]=i;
 9 }
10 
11 int find(int x)
12 {
13     return x==par[x]?x:par[x]=find(par[x]);
14 }
15 
16 void unite(int x,int y)
17 {
18     x=find(x);
19     y=find(y);
20     if(x!=y) par[x]=y;
21 }
22 
23 int main()
24 {
25     //freopen("a.txt","r",stdin);
26     int t,n,m,a,b,j=1;
27     scanf("%d",&t);
28     while(t--)
29     {
30         scanf("%d%d",&n,&m);
31         init(n*2);
32         bool flag=0;
33         for(int i=0;i<m;i++)
34         {
35             scanf("%d%d",&a,&b);
36             if(find(a)==find(b)) flag=1;
37             else
38             {
39                 unite(a+n,b);
40                 unite(a,b+n);
41             }
42         }
43         printf("Scenario #%d:
",j++);
44         if(flag) printf("Suspicious bugs found!
");
45         else printf("No suspicious bugs found!
");
46         printf("
");
47     }
48     return 0;
49 }

http://poj.org/problem?id=1703

给你两个罪犯，判断他们是否属于同一帮派，输入n个罪犯和m条关系，n个罪犯中至少有一个属于帮派Dragon，有一个属于　　帮派Snake，m条关系中A表示询问着两个人是否属于同一帮派，D表示这两个人不属于同一帮派。

这题思路跟上面一样，但开始wa了几次，对并查集的理解还是不够深。

定义并查集为：并查集里的元素i-x表示i属于帮派x（这里面有3种关系，要么是同一帮派，要么是不同帮派，要么是不能确定。）同一个并查集的元素同时成立。

初始化并查集为 2*N,如果i表示属于帮派A，那么i+N表示属于帮派B，输入两个元素不在同一帮派的时候，就合并两个帮派的元素。

这题跟上面两题一样，都是不确定元素i属于集合A还是集合B，所以要保留所有的可能性。

 1 #include <cstdio>
 2 const int maxn = 100010;
 3 int par[maxn*2];
 4 
 5 void init(int n)
 6 {
 7     for(int i=1;i<=n;i++)
 8     {
 9         par[i]=i;
10     }
11 }
12 
13 int find(int x)
14 {
15     return x==par[x]?x:par[x]=find(par[x]);
16 }
17 
18 void unite(int x,int y)
19 {
20     x=find(x);
21     y=find(y);
22     if(x!=y)
23     {
24         par[x]=y;
25     }
26 }
27 
28 int main()
29 {
30    // freopen("a.txt","r",stdin);
31     int t,n,m,a,b;
32     char s[5];
33     scanf("%d",&t);
34     while(t--)
35     {
36         scanf("%d%d",&n,&m);
37         init(n*2);
38         for(int i=0;i<m;i++)
39         {
40             scanf("%s%d%d",s,&a,&b);
41             if(s[0]=='A')
42             {
43                 if(find(a)==find(b)) printf("In the same gang.
");
44                 else if(find(a)==find(b+n)) printf("In different gangs.
");  //这里开始没想到  唉
45                 else printf("Not sure yet.
");
46             }
47             else if(s[0]=='D')
48             {
49                 unite(a,b+n);
50                 unite(a+n,b);
51             }
52         }
53     }
54     return 0;
55 }