学习笔记——拓展域并查集和带权并查集_扩展域并查集

1，拓展域并查集

        一般的并查集只能查找出各元素之间是否存在某一种相同的联系，如：a和b是亲戚关系，b和c是亲戚关系，这时就可以查找出a和c也存在亲戚关系。但如果存在多种相对的联系时一般的并查集就不行了，这时就需要对并查集进行拓展。即根据存在相对的关系数量把并查集的元素分出多份。

如：1~n各元素中，存在相同和相对的关系，那么就把各元素都分成x和x+n两部分，分别表示为和x相同的部分及和x相对的部分，当x和y相同时，则把x和y相连接，把x+n和y+n相连接(x和y相同也代表x相对的和y相对的是相同的)，当x和y相对时，则把x和y+n相连接，把x+n和y相连接(即x和y相对的是相同的，x相对的和y是相同的)。

例1：P1525 [NOIP2010 提高组] 关押罪犯

题目描述

S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1−N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

该题每两个罪犯间存在两种相对的关系，在同一个监狱和在不同的监狱 ，因此将每个元素分成x(在同一个监狱里的)和x+n(在不同监狱的)就可以了，由于要求影响力最小的，所以把怨气值从大到小排序，然后遍历，如果x和y不存在关系则把两者分开到不同监狱(x连y+n，x+n连y)，如果存在关系并且x的根等于y的根，则表示x和y在同一监狱，然后把他俩间的怨气值输出就行(因为是从大到小排序，他们之后的怨气值必然会比他们的小)。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e4 + 5;
typedef struct NODE node;
struct NODE{
	int x, y, z;
	bool operator < (const node &a) const
	{
		return z > a.z; 
	}
};
node nums[100005];
int n, m;
int rt[2*N]; //因为要分成两份，所以并查集扩大两倍
int res = 0;
int Find(int x)
{
	if(x==rt[x]) return x;
	return rt[x] = Find(rt[x]);
}
void add(int x, int y, int z)
{
	int rx = Find(x), rrx = Find(x+n), ry = Find(y), rry = Find(y+n);
	if(rx!=ry && rx!=rry) //当x和y即不在同一个监狱也不在不同的监狱时，表示还没记录，所以把他们俩分开 
		rt[rx] = rry, rt[rrx] = ry;
	if(rx==ry && rx!=rry) //当x和y在同一个监狱时，输出怨气值。 
		res = max(res, z);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=2*n; i++) rt[i] = i;
	for(int i=1; i<=m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		nums[i] = {x, y, z};
	}
	sort(nums+1, nums+m+1); //从大到小排序 
	for(int i=1; i<=m; i++)
	{
		add(nums[i].x, nums[i].y, nums[i].z);
		if(res) break; //因为是从大到小排序，所以res不为0时，必然是看到的最大的怨气值，所以直接break 
	}
	cout << res << endl;
	return 0;
}

例2：P2024 [NOI2001] 食物链

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

• 第一种说法是 1 X Y，表示 X 和 Y 是同类。
• 第二种说法是2 X Y，表示 X 吃 Y 。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

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

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

该题含三种关系，同类，吃，被吃，所以把元素分成三分，开三倍并查集数组就行。

设a分为a, a+n, a+2*n三种关系，分别代表a的同类，a吃的，吃a的.

a和b是同类时，则a和b连，a+n和b+n连，a+2*n和b+2*n连;

a吃b时，则a和b+2*n相连(即a和吃b的是同类)，a+n和b相连(a吃的和b是同类)，a+2*n和b+n相连(吃a的和b吃的是同类);

a被b吃时，a和b+n相连，a+n和b+2*n相连，a+2*n和b相连。

代码：

// 将一个个体分为三个个体: x, x+n, x+2*n , 分别表示为 和x同类， x吃的， 吃x的； 
// a和b同类时， 则a和b相连，a+n和b+n相连， a+2*n和b+2*n相连；
// a吃b时， 则a和b+2*n相连，a+n和b相连， a+2*n和b+n相连； 
#include<iostream>
using namespace std;
const int N = 5e4 + 5;
int rt[3*N] = {0}; //因为把一个个体扩展成3分，所以并查集数组扩大三倍。 
int n, k;
int cnt = 0;//假话的数量 
int Find(int x)
{
	if(x==rt[x]) return x;
	return rt[x] = Find(rt[x]);
}
void add(int x, int y, int z)
{
	int rx = Find(x), ry = Find(y);
	if(z==1)
	{
		if(rx!=ry && rx!=Find(y+n) && rx!=Find(y+2*n)) //当x和y既没记录为同类，也没记录为吃与被吃的关系时，根据要求合并记录 
			rt[rx] = ry, rt[Find(x+n)] = Find(y+n), rt[Find(x+2*n)] = Find(y+2*n);
		else if(rx==Find(y+n) || rx==Find(y+2*n)) //当x与y是吃或被吃关系时， 与话语相悖，假话加一
			cnt ++;
	}
	else //和上同理 
	{
		if(rx!=ry && rx!=Find(y+n) && rx!=Find(y+2*n))
			rt[rx] = Find(y+2*n), rt[Find(x+n)] = ry, rt[Find(x+2*n)] = Find(y+n);
		else if(rx==ry || rx==Find(y+n))
			cnt ++;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for(int i=1; i<=3*n; i++) rt[i] = i;
	for(int i=0; i<k; i++)
	{
		int x, y, op;
		cin >> op >> x >> y;
		if((op==2 && x==y) || x>n || y>n) //当x吃x时和x或y大于n时，假话加一 
		{
			cnt ++;
			continue;
		}
		add(x, y, op);
	}
	cout << cnt << endl;
	return 0;
}

2，带权并查集

普通的并查集只能查找各元素之间是否存在联系，而不能获得两连接着的元素节点之间的具体信息。带权并查集，就是在并查集中各节点连接其父节点或根的边上加上权值。权值表示着的是连接着的两节点之间的相对关系。(据说带权并查集可以解决所有拓展域并查集问题，不知道是不是真的)

一般并查集：

 带权并查集：

 既然带权并查集的边带了权值，那么在其两个集合合并和路径压缩时，其权值也应该更新。

路径压缩时，该节点的权值直接加上其父节点到它父节点的权值即可。

示意图：

代码实现：

int Find(int x)
{
	if(x!=rt[x])
	{
		int t = rt[x]; //保存它父节点 
		rt[x] = Find(rt[x]); //路径压缩 
		value[x] += value[t]; //当前节点的权值加上它父节点到根的权值
		//注：上式不一定相加，根据相对关系的不同，可能是相加，也可能是取模，异或，同或运算 
	}
	return rt[x];
}

合并时，一般的并查集只要将双方的根节点连在一起就行，但带权并查集因为带权，所以要更新被合并一方根的权值。

示意图：

这里有点不好理解，我的理解是，先把y的根节点ry连在x上，已知y到x的权值是v3，y到ry的权值是v2，那么ry到x的权值就是v3-v2，然后x到根节点rx的权值是v1，所以ry到rx的权值就是v3-v2+v1（当然不一定是加减，还有可能是异或，同或或者取模运算之类的）。

代码如下：

void add(int x, int y, int value)
{
	int rx = Find(x), ry = Find(y);
	if(rx!=ry)
	{
		rt[rx] = ry; //合并 
		v[rx] = value - v[x] + v[y]; //更新被合并一方根节点的权值。不一定是加减，这里只是举例。 
	}
}

例3:P1196 [NOI2002] 银河英雄传说

题目背景

公元 5801 年，地球居民迁至金牛座 \alphaα 第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

宇宙历 799 年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

题目描述

杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成 30000 列，每列依次编号为 1,2,…,30000。之后，他把自己的战舰也依次编号为 1,2,…,30000，让第 i 号战舰处于第 i 列，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为 M i j，含义为第 i 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 j 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第 i 号战舰与第 j 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

 要判断两战舰是否在同一列很简单，就是普通的并查集都可以解决，关键是要如何求出两战舰之间的战舰数，这时就可以用带权并查集了。这题和其他带权并查集有点不同的是，它不是给你两点之间的权值，而是要你求两点之间的权值。而其他地方和其他带权并查集一样。既然没给两点之间的value，那么合并时，被合并根节点权值的更新方式就要改变，根据题意可知，每次合并时，是把被合并方的头舰队(根节点)放到合并方的尾，所有可以得出被合并方根节点的权值为合并方的总舰队数，因此开个sum数组存每列舰队的舰队数就行了，更新方式为：v[rx] += sum[ry];

代码：

#include<iostream>
#include<cmath>
using namespace std;
const int N = 3e4 + 5;
//rt是并查集数组，v表示该舰队前面的舰队数(到根的权值)， sum表示该舰队的舰队总数 
int rt[N], v[N], sum[N]; 
int Find(int x)
{
	if(x!=rt[x])
	{
		int t = rt[x];
		rt[x] = Find(rt[x]);
		v[x] += v[t]; //更新该节点到根节点的权值 
	}
	return rt[x];
}
void add(int x, int y)
{
	int rx = Find(x), ry = Find(y);
	if(rx!=ry)
	{
		rt[rx] = ry;
		v[rx] += sum[ry]; //更新被合并方根节点到新根节点的权值 
		sum[ry] += sum[rx]; //更新当前集合的节点总数，即战舰总数 
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	for(int i=1; i<=30000; i++) rt[i] = i, sum[i] = 1, v[i] = 0;//最初时舰队各列总数为1，到头舰队的权值为0（因为它们本身就是头舰队）
	while(T--)
	{
		char c;
		int x, y;
		cin >> c >> x >> y;
		if(c=='M')
			add(x, y);
		else
		{
			if(Find(x)!=Find(y)) cout << -1 << endl; //根节点不同，代表不在同一列 
			else
				cout << abs(v[x]-v[y])-1 << endl; //求两节点间的权值 
		}
	}
	return 0;
} 

例四：P2024 [NOI2001] 食物链

又是这题，这题也可以用带权并查集去做。

我们假设A和B是同类是0，A吃B是1， B吃A是2，那么：

A->B 为1， B->C 为1，则A->C 为2；

A->B 为1， B->C 为0，则A->C 为1；

A->B 为0， B->C 为0，则A->C 为0；

所以我们可以发现，权值更新的公式为：(v[x]+v[rx]) % 3;

代码：

#include<iostream>
using namespace std;
const int N = 5e4 + 5;
int rt[N], v[N];
int cnt = 0;
int Find(int x)
{
	if(x!=rt[x])
	{
		int t = rt[x];
		rt[x] = Find(rt[x]);
		v[x] = (v[t] + v[x]) % 3;
	}
	return rt[x];
}
void add(int x, int y, int z)
{
	int rx = Find(x), ry = Find(y);
	if(rx!=ry)
	{
		rt[rx] = ry;
		v[rx] = (z - 1 - v[x] + v[y]) % 3;//减1是因为题目给出的1是同类，2是吃，而这里是0是同类，1是吃 
	}
	else
	{
		int ans = (v[x] - v[y] + 3) % 3; //加3是为了防止为负值 
		if(ans!=z-1) cnt ++;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, k;
	cin >> n >> k;
	for(int i=1; i<=n; i++) rt[i] = i, v[i] = 0;
	while(k--)
	{
		int op, a, b;
		cin >> op >> a >> b;
		if(a>n || b>n || (a==b && op==2))
		{
			cnt ++;
			continue;
		}
		add(a, b, op);
	}
	cout << cnt << endl;
	return 0;
}

例五：P1525 [NOIP2010 提高组] 关押罪犯

这题也可以用带权并查集去做。 

假设，x和y处于同一监狱为1，不同监狱为0。那么：

x->y = 0,  y->z = 0, 则 x->z = 1;

x->y = 1,  y->z = 0, 则 x->z = 0;

x->y = 1,  y->z = 1, 则 x->z = 1;

所以可以看出权值更新的公式为：x 同或 y;

代码：

#include<iostream>
#include<algorithm> 
using namespace std;
const int N = 2e4 + 5, M = 1e5 + 5;
typedef struct NODE node;
int rt[N], v[N], res = 0;
struct NODE{
	int x, y, z;
	bool operator < (const node &a) const
	{
		return z > a.z;
	}
} nums[M];
inline int XNOR(int x, int y)
{
	return x==y;
}
int Find(int x)
{
	if(x!=rt[x])
	{
		int t = rt[x];
		rt[x] = Find(rt[x]);
		v[x] = XNOR(v[x], v[t]); //权值更新 
	}
	return rt[x];
}
void add(int x, int y, int z)
{
	int rx = Find(x), ry = Find(y);
	if(rx!=ry)
	{
		rt[rx] = ry;
		v[rx] = (XNOR(XNOR(v[x], 0), v[y])); //因为要把x和y分开，所以value值为 0 
	}
	else
	{
		int ans = XNOR(v[x], v[y]);
		if(ans==1) res = z;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=n; i++) rt[i] = i, v[i] = 1; //自己和自己在同一个监狱，所以v为0 
	for(int i=0; i<m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		nums[i] = {x, y, z};
	}
	sort(nums, nums+m);
	for(int i=0; i<m; i++)
	{
		if(res) break;
		add(nums[i].x, nums[i].y, nums[i].z);
	}
	cout << res << endl;
	return 0;
}