本文主要是介绍poj1703 Find them,Catch them 【并查集】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
做过一些的带权并查集，再来做所谓的“种类并查集"，发现好像就顿悟了。
种类并查集与带权并查集实质上的差别并不大， 关键的区别就是种类并查集只是带权并查集再弄个%取余操作而已，然后余数就表示他属于哪个种类。
这题只有两个种类，也就是只有0和1两种， 对于两个不同的种类，那么之间的权值是相差1的，所以按照带权并查集的方法做加上1，然后取余2即可。
#include<cstdio>const int N = 100005;
int n, m, f[N], rank[N];inline 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])&1;return f[x];
}inline 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]+1)&1;
}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.");}elseputs("Not sure yet.");}}}return 0;
}
这篇关于poj1703 Find them,Catch them 【并查集】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
