网页设计教程 罗云芳吴黎/seo专业培训费用

题目链接：poj 1703 Find them, Catch them

题目大意：在城市中有两个大的帮派，Gang Dragon 和Gang Snake，先在有n个人被抓了，警察队他们进行m次操作，操作分为两种，询问A a b， 要求判断a和b是不是属于同一个团伙，D a b 表示说a b不属于同一个团伙。

解题思路：带权并查集的简单版，权值为1表示和前一个人不属于同一个团伙，为0表示属于同一个团伙。

#include <stdio.h>
#include <string.h>const int N = 1e5+5;
int n, m, f[N], v[N];int getfar(int x) {if (x != f[x]) {int t = f[x];f[x] = getfar(f[x]);v[x] = (v[x] + v[t]) % 2;}return f[x];
}void init () {scanf("%d%d", &n, &m);for (int i = 0; i <= n; i++)f[i] = i;memset(v, 0, sizeof(v));
}int main () {int cas, a, b;char str[10];scanf("%d", &cas);while (cas--) {init ();for (int i = 0; i < m; i++) {scanf("%s%d%d", str, &a, &b);int p = getfar(a), q = getfar(b);if (str[0] == 'A') {if (p != q)printf("Not sure yet.\n");else if (v[a] == v[b])printf("In the same gang.\n");elseprintf("In different gangs.\n");} else {if (p != q) {f[q] = p;v[q] = (v[a] + 1 - v[b])%2;}}}}return 0;
}