在并查集的实际应用中，我们经常遇到下列这种情况的题目
当满足
1、x，y为不同集合的元素
2、x，z为不同集合元素
时，y，z为相同集合的元素
如何来描述这种不同集合元素的关系就是我们接下来要学习的内容了
我们知道并查集可以用来描述相同集合的元素，所以我们可以根据这一特性稍做手脚。
当x和y为不同集合的元素时，我们令x+n和y属于同一集合，相对的x和y+n属于相同集合
故此当Same(x,y)或Same(x+n,y+n)为真时，x和y属于同一个集合
当Same(x+n,y)或Same(x,y+n)为真时,x和y属于不同集合
否则x,y的关系不确定
例题poj1703
参考代码
注意：请先自己尝试书写代码，尽量不要看我的代码
#include<stdio.h>
#define N (2 * 100100)
int pa[N];
void init(int n){
for(int i = 0; i <= 2 * n; i++)
pa[i] = i;
}
int findset(int x){
return pa[x] == x ? x : pa[x] = findset(pa[x]);
}
void Union(int x, int y)
{
x = findset(x);
y = findset(y);
if(x != y)
pa[x] = y;
}
bool Same(int x, int y)
{
x = findset(x);
y = findset(y);
return x == y;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
init(n);
while(m--)
{
char c;
int x,y;
getchar();
scanf("%c %d %d",&c,&x,&y);
if(c == 'D')
{
Union(x,y+n);
Union(x+n,y);
}
if(c == 'A')
{
if(Same(x,y) || Same(x+n,y+n)) printf("In the same gang.\n");
else if(Same(x,y+n) || Same(x+n,y)) printf("In different gangs.\n");
else printf("Not sure yet.\n");
}
}
}
return 0;
}
