`
阿尔萨斯
  • 浏览: 4109605 次
社区版块
存档分类
最新评论

poj 1703 Find them, Catch them(带权并查集)

 
阅读更多

题目链接: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");
				else
					printf("In different gangs.\n");
			} else {

				if (p != q) {
					f[q] = p;
					v[q] = (v[a] + 1 - v[b])%2;
				}
			}
		}
	}
	return 0;
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics