题目链接：http://poj.org/problem?id=1703
已经不是第一次接触种类并查集了，直到今天才搞懂。
感谢红黑联盟，感谢杰哥！！！
每个节点只要关系确定，不管是不是同一个集合里面，都把他们放到一个集合里面，用一个rank[]数组记录他们与根节点的关系，比较神奇的地方有两处：
1、find函数里面,因为find是递归写的，不断往上找，不断更新rank[x](与根节点的关系)，这个%k，也是很牛逼的，2种类型，标号只有01；
2、Union函数里面，更新rank[fy],rank[y]这里是(rank[x] - rank[y] +T)%2,这里特值法证明一下吧，我智商已经不够用了，比如说，新的节点0，合并后，就往上找，比如说找到了110,这个点肯定不是跟根同一个集合，0-A,0-B,然后(0-0+1)%2==1;
啊哈，特例搞一下吧，脑容量不够了。
#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 fx=find(x), fy=find(y);
if(fx==fy) return false;
f[fy] = fx;
rank[fy] = (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 ;
}