题目链接：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] +1)%2,这里特值法证明一下吧，我智商已经不够用了，比如说，新的节点0，合并后，就往上找，比如说找到了110,这个点肯定不是跟根同一个集合，0-A,0-B,然后(0-0+1)%2==1;
啊哈，特例搞一下吧，脑容量不够了。
#include<cstdio> const int N = 100005; int n, m, f[N], rank[N]; void init() { for(int i=1; i<=n; ++i) f[i]=i,rank[i]=0; } 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])%2; 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]+1)%2; } 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=0; 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 0; }
原文：http://www.cnblogs.com/TreeDream/p/5719016.html