「洛谷日报第87期」浅谈并查集优化

并查集是一种可以动态维护若干个不重叠的集合，并资瓷合并与查询的数据结构（这么水不配叫数据结构）

（接下来的内容过于菜，请大佬出门左转）

并查集最基本的操作是查询与合并，为了提高效率，我们常用的我们引入了路径压缩与按秩合并两种思想

路径压缩（最常用）：

给大家放张图理解下路径压缩的工作原理：

路径压缩的效率很高，可以做到 log 级别，可以防止树的形态变为一条链，在一般并查集中应用很广泛，一旦使用路径压缩，原有的父子关系就会被破坏，从而直接建立与祖先的父子关系，可以高效地维护集合之间的从属关系，但是对于每个节点之间的直接关系是不能维护的

路径压缩这里不再过多解释毕竟这么简单，我们来简述一下按秩合并，按秩合并分为按大小合并和按深度合并两种，按大小合并是很容易想到也很容易维护的，而按深度合并则是要将整个体系的从属关系抽象成一棵树，每次将深度小的合并到深度较大的树上，这样的话不论深度小的那棵树有多深，合并后的树的深度都不会大于一开始时的较大深度。

按秩合并：

而按秩合并与树的形态关系很密切，虽然不能像路径压缩一样快速处理两点是否有从属关系，它能很好地维护树的形态与父子关系，可以维护出每个子节点的直接父亲，这是路径压缩所不能做到的，由此来看，两种优化方式可以说是各有千秋。

这两种方法多数情况下是可以一起用的，既用路径压缩，又用按秩合并当然可以提高效率，不过只用路径压缩达到的效果也可以与之媲美，当然啦，依照个人习惯而定，愿意两个都用的当然可以，不过有时候按秩合并是不能与路径压缩一起使用的。仔细想一想我们刚才说到的性质，如果题目需要维护明确的父子关系而用到了按秩合并的话，是不能用路径压缩的，像上边所说，一旦用了路径压缩，会破坏树的形态，原来的节点会直接压缩到祖先上，这样一来我们调用的时候父子关系发生了改变，造成了算法的错误。

那么基础就讲到这里，下面看一下经典的扩展域和边带权问题
扩展域
首先让我们从一道题目入手：
放一道老题食物链（https://www.luogu.org/problemnew/show/P2024）

因为题目告诉我们每三种动物构成一条食物链，我们可以将每种动物分成三部分，即同类 self 、捕食 eat 、天敌 enemy ，，那我们不妨将并查集数组开大三倍，作为并查集的扩展域。
即本身对应第一倍，猎物对应第二倍，天敌对应第三倍
嗯，举个栗子
如果是同类，就合并他们本身，他们的敌人,他们的猎物

如果 x 吃 y ，说明 x 是 y 的天敌，那 x 的天敌就是 y 捕食的物种，也就是 x 吃 y ， y 吃 z ， z 吃 x

每次先判断是不是假话，也就是看一下是否已经被合并过，并且之前合并的关系与当前关系是否冲突，然后就可以按照题目所给出的关系进行合并啦~
在做这道题之前不妨先做一下这道题团伙 （https://www.luogu.org/problemnew/show/P1892）
食物链是这道题运用的反集思想的扩展，(食物链用的是三倍空间，团伙用的是二倍)做完这道题再来做食物链可能更好理解（双倍经验）

边带权

依然从一道老掉牙的题目开始银河英雄传说 （https://www.luogu.org/problemnew/show/P1196）
因为在并查集中存在着父子关系，所以也就有了树的形态，整个并查集数组就可以看成由若干棵树组成的森林，对于每个点维护一个数组d[]保存节点x到父亲节点fa[]之间的边权。
稍微放一下伪代码（逃：

因为每次路径压缩后这个点都会直接指向祖先，那么，不妨直接利用路径压缩来更新d[]（就是将维护数组的过程放在路径压缩中），这样，对于每一次询问祖先都能更新对应的边权，在最后调用结果的时候重新更新一遍就能保证其正确性。
理解了的话就再来一道 QwQ叠积木（二倍经验） （https://www.luogu.org/problemnew/show/P2342）
代码什么的我相信你会写
（不放代码就跑真开心~）

并查集求环

由于并查集能维护父子关系，所以我们也可以将它运用到图论中，比如这道题信息传递（https://www.luogu.org/problemnew/show/P2661），对于一个环，势必有一个点的父亲是他的子孙节点，（画个图很好理解的），如果发现将要成为自己父亲的节点是自己几代之后的子孙，这就说明有环出现了，用边带权并查集维护儿子是哪一代就可以求出环的大小，就可以进一步求最大环、最小环之类的东西啦，当然这只是并查集思路，这类题目还有另一种解法—— tarjan （强烈安利）就是裸的缩点。
好的，如果理解了就来看下这道加强版在农场万圣节（https://www.luogu.org/problemnew/show/P2921）
又不放代码啦啦啦

特意去学了下可持久化并查集，发现她和并查集并没有很大的关系，所以这里不介绍啦（并不是偷懒）

以上，希望我的讲解能对大家有帮助 qwq

最后希望大家 noip2018 rp++!
估计发出来的时候我已经退役了

本文发布于洛谷日报，特约作者：喵小皮

原文地址：https://www.luogu.org/blog/maioxiaopi/qian-tan-bing-zha-ji