题意：警察抓获N个罪犯，这些罪犯只可能属于两个团伙中的一个，现在给出M个条件（D a b表示a和b不在同一团伙），对于每一个询问(A a b)确定a，b是不是属于同一团伙或者不能确定。
思路：如果父亲和孩子是同一个团伙，那么孩子标记为0，如果不是的话，孩子标记为1，然后就是种类并查集的事情。
- 种类并查集
- 判断在不同的集合
- 以前接触的并查集都是让我们判断是否属于同一个连通分量，但这道题却让你判断是否属于同一类
r[x]：x所属的类
具体解释
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std; const int maxn = 100005;
int n,m;
int a,b,ans;
int pre[maxn]; //存父亲节点
int r[maxn]; //存与根节点的关系，0 代表同类， 1代表不同类
//r[i]=1 表示结点i与根结点属于一类
void init()
{
for(int i=1;i<=n;i++){
pre[i] = i; //自己是自己的父亲
r[i] = 0; //自己与自己是同一类
}
} int find(int x)
{
if(x == pre[x]) return x; int t = pre[x]; //记录父亲节点，方便下面更新r[]
pre[x] = find(t);
r[x] = (r[x]+r[t])%2; //根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系
return pre[x];
} void unite(int x,int y)
{
int rx = find(x);
int ry = find(y);
if(rx != ry){
pre[rx] = ry; //合并
r[rx] = (r[x]+1-r[y])%2; //fx与x关系 + x与y的关系 - y与fy的关系 = fx与fy的关系
}
} int main()
{
int T;
cin>>T;
while(T--){
scanf("%d%d",&n,&m);
init();
int flag=0;
while(m--){
char str[10];
scanf("%s%d%d",str,&a,&b);
if(str[0] == 'A'){
//如果根节点相同，则表示能判断关系
if(find(a)==find(b)){
if(r[a] == r[b])
cout<<"In the same gang.\n";
else
cout<<"In different gangs.\n";
}
else{
cout<<"Not sure yet.\n";
}
}
if(str[0] == 'D'){
unite(a,b);
}
}
}
return 0;
}