不相交集 / 并查集（C语言实现）

浏览数：23 / 时间：2015年06月08日

题目大意：给出n，表示有一个长度为n由01组成的序列，给出m次询问，a b odd/even 表示在a~b这个区间上1的个数是奇数还是偶数，找到最先矛盾的那条语句。

解题思路：因为n非常大，但是询问非常小，所以要将点map离散化，我的做法是用两个map来处理，一个是f数组，一个v数组，每次有一个新的区间a b，就让b->a-1，权值为1/0，表示从b到a-1这段上面1的个数为奇数还是偶数，这样就映射成了带权并查集。

#include <stdio.h>
#include <string.h>
#include <map>

using namespace std;
map<int, int> f;
map<int, int> v;
int n, m;

void judge (int x) {
	if (f.count(x)) return ;
	f[x] = x;
	v[x] = 0;
}

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];
}

int solve () {
	int a, b, ans = n;
	char str[10];
	for (int i = 0; i < n; i++) {
		scanf("%d%d%s", &a, &b, str);
		if (ans != n) continue;
		a--;
		judge(a);
		judge(b);

		int s = (strcmp(str, "odd") == 0) ? 1 : 0;
		int p = getfar(a), q = getfar(b);

		if (p == q) {
			if (s == 1 && v[a] == v[b]) ans = i;
			if (s == 0 && v[a] != v[b]) ans = i;
		} else {
			f[q] = p;
			v[q] = (v[b] + 2 + s + v[a])%2;
		}
	}
	return ans;
}

int main () {
	while (scanf("%d%d", &m, &n) == 2) {
		f.clear();
		v.clear();
		printf("%d\n", solve ());
	}
	return 0;
}

不相交集 / 并查集（C语言实现）,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

不相交集 / 并查集（C语言实现）