题目链接：http://poj.org/problem?id=1703
思路;个人觉得本质上还是和带权并查集一样的，只不过多了一个MOD操作，然后就是向量关系图稍微改动一下就变成种类并查集了，对于本题，我们可以用一个kind数组来表示是否属于同一类，其中kind[x]==0表示不是同一类，kind[x]==1表示属于同一类，这样我们就可以得到向量关系式了(若r1=Find(u),r2=Find(v),并且parent[r1]=r2,那么就有kind[v]+1==kind[u]+kind[r1])然后变形后对2取余就可以了，即kind[r1]=(kind[v]-kind[u]+1)%2，这是Union部分，还有路径压缩的时候注意更新一下kind[]就ok了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100010
int parent[MAXN];
int kind[MAXN];
//0表示不属于同一类，1表示属于同一类
int n,m; void Initiate()
{
for(int i=;i<=n;i++){
parent[i]=i;
}
memset(kind,,(n+)*sizeof(kind[]));
} int Find(int x)
{
if(x==parent[x]){
return parent[x];
}
int tmp=Find(parent[x]);
kind[x]=(kind[x]+kind[parent[x]])%;
return parent[x]=tmp;
} void Union(int u,int v)
{
int r1=Find(u),r2=Find(v);
if(r1==r2)return ;
parent[r1]=r2;
kind[r1]=(kind[v]-kind[u]+)%;
} int main()
{
// freopen("1.txt","r",stdin);
int _case,a,b;
char str[];
scanf("%d",&_case);
while(_case--){
scanf("%d%d",&n,&m);
Initiate();
while(m--){
scanf("%s%d%d",str,&a,&b);
if(str[]=='D'){
Union(a,b);
}else {
int r1=Find(a),r2=Find(b);
if(r1!=r2){
puts("Not sure yet.");
}else if(kind[a]==kind[b]){
puts("In the same gang.");
}else {
puts("In different gangs.");
}
}
}
}
return ;
}