题意：某城市存在蛇帮和龙帮两大帮派（话说名字还能再挫一点点吗. . . ）。在某一次像东莞这样的大规模的扫黄打非中，警察抓住了 n 个人，但是不缺定他们分别属于哪个帮派。现在给你一些条件，然后让你判断两个人是否属于同一个帮派。
思路：并查集的高级应用——关系并查集。与朴素的并查集相比，每个节点又多了一个权值，用来表示与其父节点的关系。当该节点为根节点时，权值无意义。
并查集的应用无非是快速查询。
当询问的两个点不在一棵树上时，两者关系无法确定。
当询问的两个点在一棵树上时，可以 通过两个节点各自与根节点的关系 来 判断两个节点的关系，当其中一点为根节点时关系更加显而易见。
可以通过在寻找根节点时判断节点与根节点之间的关系：
以此题为例，设根节点为r，查询节点为 u ,设在寻找根节点的过程中询问到的点为 v，w[]为节点与父节点的关系，v 与 u的关系为 re，re == 1 表示u ， v不属于一个帮派，re == 0时，属于一个帮派。
开始时，v == u，re = 0;若w[v] == 1,则说明v 与父节点的不属于同一帮派。re = (re == 0 1 : 0)，若 w[v] == 0 ,则 re 不变;然后 v = fa[v];直到v == fa[v]。
关系并查集的合并：
当不属于同一棵树的两个点 u , v确定关系时，要将两棵树进行合并。
仍以此题为例：
设ru，rv分别为u，v的跟节点，wu，wv分别表示u，v与跟节点的关系，w[]为节点与父节点的关系。
当wu == wv时，则表示ru和rv属于不同帮派（因为此题中，每次确定关系均为不属于同一帮派）, 则w[ru] = 1，fa[ru] = rv；
当wu != wv时，则表示ru和rv属于同一帮派 ， 则w[ru] = 0，fa[ru] = rv；
#include#include #include #include #include #include using namespace std; int fa[100100]; int re[100100]; int Re; int Find(int x) { int t = x; while(x != fa[x]) { if(re[x]) Re = (Re == 1 0 : 1); x = fa[x]; } fa[t] = x; re[t] = Re; return x; } void Merge(char c,int u,int v) { Re = 0; int fu = Find(u); int r1 = Re; Re = 0; int fv = Find(v); int r2 = Re; if(c == 'A') { if(fu != fv) { printf(Not sure yet. ); } else { if(r1 == r2) { printf(In the same gang. ); } else { printf(In different gangs. ); } } return ; } fa[fu] = fv; if(r1 == r2) { re[fu] = 1; } else { re[fu] = 0; } } int main() { int T; int n,m,i,u,v; char c; scanf(%d,&T); while(T--) { scanf(%d %d,&n,&m); for(i = 1;i <= n; ++i) { fa[i] = i; re[i] = 0; } for(i = 0;i < m; ++i) { scanf(%*c%c %d %d,&c,&u,&v); Merge(c,u,v); } } return 0; }