D： u v  u与v在不同的集合 A： u v  查询u与v的关系 1)压缩路径过程        fu->root   0  1  u-fu 0                 0  1   1                 1  0 2)合并过程 fu->fv      u->fu   0 1   v->fv 0            1 0 1            0

做过一些的带权并查集，再来做所谓的“种类并查集"，发现好像就顿悟了。 种类并查集与带权并查集实质上的差别并不大， 关键的区别就是种类并查集只是带权并查集再弄个%取余操作而已，然后余数就表示他属于哪个种类。 这题只有两个种类，也就是只有0和1两种， 对于两个不同的种类，那么之间的权值是相差1的，所以按照带权并查集的方法做加上1，然后取余2即可。 #include<cstdio>const int

种类并查集，比poj1182水 #include <iostream>#include <cstring>using namespace std;const int N=100005;int father[N];int rank[N];int n,m;void init(){memset(rank,0,sizeof(rank));for (int i=0;i<=100000;i++

找规律算出子节点与父节点，子节点与爷爷节点的关系来建图。 /*DAccepted916 KB329 msC++1120 B2013-04-08 18:29:33*/#include<cstdio>const int maxn = 100000+10;int p[maxn]; //存父亲节点int r[maxn]; //存与根节点的关系，0 代表同类， 1代表不同类int fi