题目链接：http://poj.org/problem?id=1703
第一次做种类并查集，有的地方还不是很清楚，想了一上午，有点明白了，这里记录一下。
这里我参考的红黑联盟的题解。
关键：种类并查集与带权并查集实质上的差别并不大， 关键的区别就是种类并查集只是带权并查集再弄个%取余操作而已，然后余数就表示他属于哪个种类。
rank数组表示节点和父节点的关系（也可以理解为他的种类）。
find中，找到x的父节点后，那么更新他与父节点的关系，rank[x] = (rank[x]+rank[fa])%2;
合并的时候，把b接到a下面，更新他与父节点的关系，rank[b] = (rank[x]-rank[y]+1)%2;
#include<cstdio> const int N = ;
int n, m, f[N], rank[N]; void init()
{
for(int i=; i<=n; ++i)
f[i]=i,rank[i]=;
} int find(int x)
{
if(x==f[x])
return f[x];
int fa=f[x];
f[x] = find(f[x]);
rank[x] = (rank[x]+rank[fa])%;
return f[x];
} bool Union(int x,int y)
{
int a=find(x), b=find(y);
if(a==b)
return false;
f[b] = a;
rank[b] = (rank[x]-rank[y]+)%;
} int main()
{
int T,a,b,fa,fb;
char ch;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%*c",&n,&m);
init();
for(int i=; i<m; ++i)
{
scanf("%c%d%d%*c",&ch,&a,&b);
if(ch=='D')
{
Union(a,b);
}
else
{
fa = find(a), fb=find(b);
if(fa==fb)
{
if(rank[a]==rank[b])
puts("In the same gang.");
else puts("In different gangs.");
}
else
puts("Not sure yet.");
}
}
}
return ;
}