拓展域

拓展域，个人感觉算是并查集中比较难的部分了。（网上都没什么详细的教学。。。全靠理解代码

简而言之，就是用多个并查集，多个空间，来表示节点之间的一些相互关系，比如x的敌人，x的朋友，我需要找到x的敌人的敌人，就也是我的朋友，x的敌人的朋友，就也是我的敌人。（【NOIP 2010 提高组】关押罪犯）

不多说，直接看例题吧。

（我感觉我说肯定说不清楚。。。

例题解释

1、POJ-1182 食物链

题目大意就是，告诉你一些动物之间的关系（同类或者捕食），如果满足这三个条件

1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话；

就是假话。问你假话的数量。

我们可以用在同一个并查集的表示是同一类，x+n表示捕食关系。

x->x+n->x+2*n->x

如果x和y是同类，那么

1） x和y是同一类；
2） x+n和y+n是同一类；
3） x+2 * n和y+2 * n是同一类;

如果x和y是捕食关系，那么

1） x和y+2 * n是同一类；
2） x+n和y是同一类；
3） x+2 * n和y+n是同一类;

这样就可以用三个并查集来表达之间的关系了。

#include <iostream>
using namespace std;

const int N = 5e4 + 5;
int f[3 * N + 5];

int find(int root) {
	int son = root, t;
	while (root != f[root])	root = f[root];
	while (son != root) {
		t = f[son];
		f[son] = root;
		son = t;
	}
	return root;
}

void join(int root1,int root2) {
	root1 = find(root1);
	root2 = find(root2);
	if (root1 != root2)	f[root1] = root2;
}

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 1; i <=3*n; i++) {//初始化，三倍空间
		f[i] = i;
	}
	int ans = 0;
	int d, x, y;
	while (k--) {
		scanf("%d %d %d", &d, &x, &y);
		if (x > n || y > n) {//大于n就是假话，直接continue
			ans++;
			continue;
		}
		if (d == 1) {
			if (find(x + n) == find(y) || find(x) == find(y + n))	ans++;
            //x捕食y或者y捕食x，关系不符，就是假话
			else {
				join(x, y);
				join(x + n, y + n);
				join(x + 2 * n, y + 2 * n);
			}
		}
		else {
			if (find(x) == find(y) || find(y + n) == find(x))	ans++;
            //x和y是同一类或者y捕食x，关系不符，就是假话
			else {
				join(x + n, y);
				join(x + 2 * n, y + n);
				join(x, y + 2 * n);
			}
		}
	}
	printf("%d\n", ans);
}

2、POJ-1733 Parity game

你有一串由0和1构成的序列，告诉你一些关系（[L,R]中1的个数是奇或偶），问你哪个地方出现了矛盾，输出最早出现矛盾的位置。

（这个题目。。相当头疼，想了好久，根本看不懂，我也不确定我能解释清楚。。

首先要离散化，n太大了，数组放不下，需要先离散化。

然后我们可以用d[x]表示x到根节点之间是奇是偶，用f[x]（并查集）表示前后关系。

如果根节点相同的时候，就需要判断是否矛盾。判断矛盾的时候可以用

d[x]^d[y] 表示x到y之间的1的个数

1） d[x] = 0,d[y] = 0 时，d[x]-d[y] == d[x]^d[y] == 0;
2） d[x] = 0,d[y] = 1 时，d[x]-d[y] == d[x]^d[y] == 1;
3） d[x] = 1,d[y] = 0 时，d[x]-d[y] == d[x]^d[y] == 1;
4） d[x] = 1,d[y] = 1 时，d[x]-d[y] == d[x]^d[y] == 0;

在路径压缩上，也可以使用同样的方法

d[x]^d[f[x]] 表示x到f[x]之间的1的个数（用递归来实现）

1） d[x] = 0,d[y] = 0 时，d[x]+d[y] == d[x]^d[y] == 0;
2） d[x] = 0,d[y] = 1 时，d[x]+d[y] == d[x]^d[y] == 1;
3） d[x] = 1,d[y] = 0 时，d[x]+d[y] == d[x]^d[y] == 1;
4） d[x] = 1,d[y] = 1 时，d[x]+d[y] == d[x]^d[y] == 0;

关系表示完后，即可写出正确代码。

（。。。我觉得没那么简单，我是真的菜。。根本想不到的好吧

#include <iostream>
#include <map>
using namespace std;

const int N = 5050;
int f[2 * N], d[2 * N];
map<int, int> num;//n太大了，不能用数组

int search(int root) {
	if(root != f[root]) {
		int t = search(f[root]);//递归寻找根节点
		d[root] = d[root] ^ d[f[root]];//更新d[x]的值
		f[root] = t;
	}
	return f[root];
}

int join(int x, int y, int l) {
	int rx = search(x);
	int ry = search(y);
	if (rx == ry) {
		if ((d[x] ^ d[y]) != l)	return 0;//判断是否矛盾
		else return 1;
	}
	else {
		f[ry] = rx;
		d[ry] = (d[x] + d[y] + l) % 2;
        //d[ry] = (d[x] ^ d[y] + l) % 2;也可
	}
	return 1;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= 2 * N - 5; i++) {
		f[i] = i;
	}
	int cnt = 1, mark = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, l;
		char ch[10];
		cin >> x >> y >> ch;
		if (!num[x - 1])	num[x - 1] = cnt++;//离散化
		if (!num[y])	num[y] = cnt++;
		if (ch[0] == 'e')	l = 0;
		else l = 1;
		if (!join(num[x - 1], num[y], l)) {
			mark = i;
			break;
		}
	}
	if (!mark)	mark = m + 1;//如果没有冲突，就输出m
	cout << mark - 1 << endl;
}