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。
#include <cstdio>
const int maxn = ;
int par[*maxn]; void init(int n)
{
for(int i=;i<=n;i++)
par[i]=i;
} int find(int x)
{
return x==par[x]?x:par[x]=find(par[x]);
} void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y) par[x]=y;
} int main()
{
//freopen("a.txt","r",stdin);
int t,n,m,a,b,j=;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init(n*);
bool flag=;
for(int i=;i<m;i++)
{
scanf("%d%d",&a,&b);
if(find(a)==find(b)) flag=;
else
{
unite(a+n,b);
unite(a,b+n);
}
}
printf("Scenario #%d:\n",j++);
if(flag) printf("Suspicious bugs found!\n");
else printf("No suspicious bugs found!\n");
printf("\n");
}
return ;
}
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，所以要保留所有的可能性。
#include <cstdio>
const int maxn = ;
int par[maxn*]; void init(int n)
{
for(int i=;i<=n;i++)
{
par[i]=i;
}
} int find(int x)
{
return x==par[x]?x:par[x]=find(par[x]);
} void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
{
par[x]=y;
}
} int main()
{
// freopen("a.txt","r",stdin);
int t,n,m,a,b;
char s[];
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init(n*);
for(int i=;i<m;i++)
{
scanf("%s%d%d",s,&a,&b);
if(s[]=='A')
{
if(find(a)==find(b)) printf("In the same gang.\n");
else if(find(a)==find(b+n)) printf("In different gangs.\n"); //这里开始没想到 唉
else printf("Not sure yet.\n");
}
else if(s[]=='D')
{
unite(a,b+n);
unite(a+n,b);
}
}
}
return ;
}