并查集汇总
date
Feb 6, 2023
slug
disjoint-set
status
Published
tags
算法
summary
朴素并查集、带权并查集、种类并查集
type
Post
用途
并查集一般用于管理元素所属集合，是一种数据结构，一般有两个操作：
- 合并两个集合
- 判断两个元素是否属于同一集合
朴素并查集
一般这种并查集是我们最常用的结构，为了区分，我把它成为朴素并查集。
原版
原版的并查集就是实现了开头介绍的合并、判断两个操作。
维护size的并查集
可以使用一个size数组来记录集合存在的元素，合并的时候让元素少的集合往元素多的集合合并。
这种合并方式也被称为启发式合并。
相比于原版的合并，效率会高一些。
带权并查集
维护到祖先节点距离的并查集
带权的合并操作
我们看一个具体的例子，假设有x和y两个节点，他们的距离是w，而px和py分别是两个节点的祖先节点，它们到祖先的距离分别是d[x]和d[y]。
现在想要合并px到py，问题是我们怎么设置px和py的距离？
经过观察后发现，合并后x→px→py和x→y→py的距离应该相同，如果不相同就矛盾，因此可以得到
d[px] = w + d[y] - d[x]，这是一般情况下权值的计算方式。在实际题目中，可以根据题目的描述来修改合并方式。
find函数
需要注意的是这里的find函数，一开始
d[x]实际上表示的是当前节点离p[x]的距离，而当进行路径压缩后，p[x] 就是这个集合的祖先节点，那么d[x] 的含义就变为了当前节点到祖先节点的距离。所以我们必须先进行路径压缩，才能更新d[x]
如果先更新
d[x]，再进行压缩，那么就会得到错误的数据：这样写就不能正确更新了。
种类并查集
上面我们介绍的并查集，维护的信息都是具有连通性、传递性的，比如说朋友的朋友是朋友。但有时候题目要求我们维护敌人的敌人是朋友这种关系，种类并查集就是为了解决这个问题而诞生的。
假设需要总元素个数是n，题目需要将维护朋友和敌人两种关系，那么我们就开2n的空间，这里假设n=4。
我们用1~4维护朋友关系（比如说关在同一个监狱的狱友），用5~8维护敌人关系（比如说关在不同监狱的仇人）。现在假如我们得到信息：1和2是敌人，应该怎么办？
我们
merge(1, 2+n), merge(1+n, 2);。这里的意思就是：1是2的敌人，2是1的敌人
假设2和4又是敌人，我们同样
merge(2, 4+n), merge(2+n, 4)
由于敌人的敌人是朋友，我们可以得出1和4是朋友。当我们查询1和4是否属于同一集合的时候，得到的结果是true。
通过上面的例子我们可以总结一般性规律：
- 题目有
n个元素，有m种类别，则我们需要开n * m的空间
1*n, 2*n, 3*n, …, m*n分别代表不同的类别
- 通过链接不同类别的节点，可以描述某种关系。
复杂度
复杂度的详细讨论请看：并查集 - OI Wiki (oi-wiki.org)
默认情况下，我们可以认为并查集的每个操作时间复杂度都是很小的常数，近似
空间复杂度是
练习题
下面我们看一些经典的并查集题目，来了解并查集的应用：
银河英雄传说
题目大意：
N个飞船分布在N列，给定两种操作：
M i j 将第i列的飞船保持原有顺序，接在第j列的尾部C i j 询问第i号战舰与第j号战舰是否处于同一列，如果同一列，输出它们所隔的战舰。可以看到题目有很强的集合特征，用并查集来做最合适了
对于
M操作，我们执行合并，对于C操作，我们查询i和j是否是同一个集合，如果不是输出-1，否则输出abs(d[i] - d[j]) - 1，其中d[i]表示i节点到祖先节点的距离初始化时，将
d[i]初始化为1，在我们执行合并的时候，假设要执行M 3 2，当前状态如图：
那么
3→2这条边，值应该是多少呢？考虑合并后，
3和6的祖先节点均变为4，而M操作要求我们把节点接在目标集合的尾部，那么3→2的权值应该更新为4，同样地，6→3的权值应该加上4。我们把结论变得更具有概括性：执行
M i j操作时，属于i集合的节点的权值，应该加上j集合的元素个数s[j]。
现在问题是怎么给
i集合的所有权值加上s[j] 呢？我们需要找出所有属于i集合节点的元素然后添加s[j]吗？实际上并查集的路径压缩能很方便的实现这个操作。还是上面的例子，一开始
d[3] = 0 当我们执行M 3 2 的时候，会设置d[3] = s[4] 。只需要执行这步操作后，再将来find的时候，由于路径压缩的原因：当我们
find(6) 的时候，其中d[x] += d[p[x]] 这步操作，会把先前更新的d[3]累加到d[6] 上。从而保证了从6出发，到祖先节点的d都能被正确更新。总而言之我们只需要修改
i集合祖先节点的d，后续就能通过find操作来更新集合中所有节点的d。下面我们就可以根据分析内容和带权并查集的模板写出代码了：
食物链
带权并查集
这道题可以用带权并查集做，我们假设此时的权值
d[i]的含义是当前节点i和祖先节点的关系。根据题目的定义，无非是三种关系：同类、吃、被吃，我们用0，1，2分别来表示这三种关系：
- d[i] = 0 → 和根节点同类
- d[i] = 1 → 吃根节点
- d[i] = 2 → 被根节点吃
举一个例子，下面图中，x是祖先节点，
d[y] = 1 表示y吃根节点，d[z] = 2 表示z被根节点吃，d[k] = 3, d[k] % 3 = 0 表示k和x是同类。我们可以根据d的值推断出任意两个节点的关系，比如说z和y就是z吃y的关系，而k和y是同类。
根据上面的定义，我们现在考虑任意两个节点
x和y, x ≠ y- 如果x和y在同一集合
- 如果x和y是同类，那么
(d[x] - d[y]) % 3 = 0成立。 - 这里表示x和y都和根节点是同类，因此x和y是同类
- 如果x吃y，那么
(d[x] - d[y] - 1) % 3 = 0成立 - 这里表示x吃根节点，而y和根节点是同类，因此x吃y
- 如果x被y吃，那么
(d[x] - d[y] - 2) % 3 = 0成立
这里需要取模，是因为d[x]的值很有可能超过3，所以我们用%3来约束d[i]的值域，便于判断。
- 如果x和y不在同一个集合，则需要合并，方便以后判断
- 如果x和y是同类，那么
(d[x] + d[px] - d[y]) % 3 = 0成立，可以推断出d[px] = (d[y] - d[x]) %3 - 如果x吃y，那么
(d[x] + d[px] - d[y] - 1) % 3 = 0成立，可以推断出d[px] = (d[y] - d[x] + 1) %3
比如说上面的情况，给定x和y，以及它们的祖先节点px和py，还有距离d[x]和d[y]，想要合并px到py，那么d[px]应该等于多少呢？
经过上面讨论，我们已经可以判断任意两个节点之间的关系了，接下来就可以写出答案了。
题目给出的两类语句：
1 x y表示x和y是同类2 x y表示x吃y在我们拿到一个语句的时候，我们先判断这个语句是否是假话，如果是假话，我们什么都不做，否则的话当前话是真话，我们根据真话来执行相应操作，比如说如果x和y属于不同集合，且当前话是真话，那么就要合并x和y的两个集合，方便后续判断
种类并查集
当前有三类元素，我们开3n的空间。用i + n来表示i的捕食对象，i+2n来表示i的天敌。
这三类集合如果存在联系，那么就是某种关系存在，举个例子
如果(x, y + 2n) 存在一条边，那么就表示 y 是 x 的天敌
如果(x, y + n) 存在一条边，那么就表示 x 吃 y
关押罪犯
种类并查集
我们可以按照边权降序排序，优先将大的边分布在集合之间，就是优先把大冲突的两个节点关在不同监狱，直到无法这么做（无法安排在不同监狱），此时的冲突就是最小的冲突。
显然我们可以分为两类元素，那么需要2 * n的空间。n ~ 2*n 表示敌人。
带权并查集
这道题目也可以用带权并查集+二分来做。
假设答案是mid，那么所有大于mid的边中，边的两端x和y是不连通的，就是说它们属于不同的类别。那么我们可以使用二分来枚举mid，使用一个
check()函数来判断当前枚举值是否可行。check 函数的细节就是，对于所有大于mid的边，如果我们发现两个端点是同一类中，那么就返回false，重复直到没有边，返回true。如何描述两个点是否属于同一类，可以用带权并查集来实现，0 和 1 分别表示两个类别。
接下来我们可以写出代码：
当然这里也可以把带权并查集换成种类并查集，同样用二分解决，不过直接用种类并查集的性质比较优雅。
总结
本文介绍了朴素并查集，带权并查集，种类并查集，这里总结一下他们的区别
- 朴素并查集：最常用的一类并查集，用来管理元素的从属关系。
- 带权并查集：在朴素并查集上添加了权重
d，d可以根据题目的不同来表示不同的含义，使用时需要确定merge和find操作如何更新d
- 种类并查集：一般维护若干个n的区间，每个区间表示不同含义，通过merge不同区间的节点，标识某种关系的存在
一般种类并查集都可以用带权并查集来做，我们定义好d的含义即可，而且只有总节点数的比较小情况下才能用种类并查集，不然开若干个区间可能会溢出。但是种类并查集的思想和含义也比较简洁，有的时候可以利用它的性质来巧妙解题。
Ref
更多例题：
hdu1232 城镇交通
poj1611 感染的学生
hdu3038
POJ2492