題目鏈接：http://poj.org/problem?id=1703
題目大意：警察抓獲N個罪犯，這些罪犯只可能屬于兩個團伙中的一個，現在給出M個條件（D a b表示a和b不在同一團伙），對于每一個詢問(A a b)確定a，b是不是屬于同一團伙或者不能確定。
思路：一般的并查集題目都是給出a，b屬于同一集合，但是這題不同，給出的a,b不在同一集合，如果用其他方法可能太復雜，在此介紹一種此類問題的通法：
定義數組pre[x]表示x的父節點，r[x]表示x與當前所在集合的代表元的關系，0表示x與代表元屬于同一團伙，1表示不在同一團伙，初始值都為0，因為自己肯定和自己在同一團伙。
?
合并兩個元素a，b的時候：
void Union(int x,int y)
{
??????? int xx=find(x);????????? // ?1
????????int yy=find(y);?????????// ?2
??????? pre[xx]=yy;???????????? // ?3
??????? r[xx]=(r[y]+r[x])^1;?? //? 4
}
對于1,2,3句話，不用解釋，與一般的并查集合并操作一樣（沒用啟發式合并），而對于第4句話，既然把代表元為xx的集合合并到了代表元為yy的集合，那么xx與他現在的集合的代表元（也就是yy）的關系r[xx]肯定是要改變的，至于怎么改變，可以枚舉所有情況然后找出規律（聽說可以用向量方法想，但是現在不懂）。同樣的，原來以xx為代表元的集合中的所有元素的r[]值都可能發生改變，那么在此是不是要把所有的元素的r都改變一次呢，答案是否定的，我們可以再find（）操作里面改變。
?
查找操作：
int find(int x)
{
?if(x!=pre[x])
?{
??int f=pre[x];????????????????? // 1
??pre[x]=find(pre[x]);
??r[x]=(r[x]+r[f])%2;?????? //? 2
?}
?return pre[x];
}
第1句話，先把原來x的父節點保存起來，然后路徑壓縮的時候就已經把r[pre[x]]修改了，然后接下來就是修改r[x]，r[x]的值與r[f]的值的關系很好推，就是r[x]=(r[x]+r[f])%2。
#include"stdio.h"
int f[100005];
int r[100005];
void set(int n)
{int i;for(i=1;i<=n;i++){f[i]=i;r[i]=0;}
}
int find(int x)
{int t;if(x!=f[x]){t=f[x];f[x]=find(f[x]);r[x]=(r[x]+r[t])%2;}return f[x];
}
void Union(int x,int y)
{int xx,yy;xx=find(x);yy=find(y);f[xx]=yy;r[xx]=(r[x]+r[y])^1;
}
int main()
{int a,b,t,n,m,aa,bb;char s[3];scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);set(n);while(m--){scanf("%s%d%d",s,&a,&b);if(s[0]=='A'){aa=find(a);bb=find(b);if(aa==bb&&r[a]!=r[b])printf("In different gangs.\n");else if(aa==bb&&r[a]==r[b])printf("In the same gang.\n");elseprintf("Not sure yet.\n");}else Union(a,b);}}return 0;
}
)
