前言

去写了并查集的题,就来写了。

正文

简单描述一下并查集是干嘛的吧,我们可以把它想象成家族。
刚刚开始的时候,每个人各成帮派,后面有一些帮派结盟,互相合并,当然一个人只可能在一个帮派里,盟主可不允许自己的成员脚踏两条帮派。
每一个帮派的成员都只知道自己的直系上级,想知道盟主必须一层一层向上询问...这很麻烦,于是就想到了,让每个人都知道上级是盟主,这就是路径压缩
大帮派去小帮派需要大包大包打包东西搬家,很麻烦,于是就想到让小帮派去到大帮派合并,让大帮派的盟主成为盟主,小帮派的盟主成为大帮派盟主的直系下级,这就是按秩合并,也就是启发式合并
帮派里有令牌流通,而每个人都知道自己的直系下属的令牌数量,这就是“边带权”,在路径压缩的时候可以同时更新令牌的值,这样子就可以统计每个人到盟主的路径上的一些信息。
如果用更抽象的语言解释的话,并查集就是可以动态维护若干个不重叠的集合,并且支持合并与查询的数据结构。
为了实现并查集这种数据结构,可以采用“代表元”法,为每个集合选择一个固定的元素,作为整个集合的“代表”。
我们使用一个树形结构存储每个集合,树上的每个节点都是一个元素,树根是集合的代表元素。
那么整个并查集就是一个森林,可以维护一个数组fa来记录这个森林,用fa[x]保存x的父节点,特别的,树根的父节点是其自己。
合并两个集合的时候,只需要连接两个树根(令一个树根成为另一个树根的子节点),在查询元素的归属的时候,需要从该元素开始通过fa存储的值不断递归访问父节点,直至达到树根(父节点是自己的节点)。
为了提高效率,并查集引入了路径压缩按秩合并两种思想。
为了更快找到树根,我们可以在每次查询的同时,把访问过的每个节点(也就是所查询元素的全部祖先)都直接指向树根,这种优化方法称为路径压缩
还有一种优化方法被称为按秩合并,我们这里把“秩”定义为集合的大小,在合并的时候把“秩”较小的树根作为“秩”较大的树根的子节点,此时这种方法也被称为“启发式合并”
同时采用路径压缩按秩合并优化的并查集,每次查询的均摊复杂度可以进一步降到O(α(N)),其中α为反阿克曼函数,更准确的说,α(x)定义为最大的整数m使得Ackermann(m, m) ≤ x,其中Ackermann为阿克曼函数。
这是一个增长的很慢的函数,对于∀N ≤ (2 ^ (2 ^ (10 ^ 19729))),都有 α(N) < 5,故α(N)可以近似为一个常数。具体参见著名计算机科学家 R.E.Tarjan 于 1975年发表的论文。
Tarjan,Robert Endre (1975), Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM. 22 (2): 215-225
Tarjan,Robert Endre (1975), Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM. 22 (2): 215-225

“边带权”并查集

并查集实际上是由若干树构成的森林,我们可以在树中的每条边上记录一个权值,即维护一个数组d,用d[x]保存节点x到父节点fa[x]之间的边权,在每次路径压缩的时候我们同时更新这些d值,这样子就可以统计每个节点到树根之间路径上的一些信息。这就是所谓的“边带权”并查集

Tips

“扩展域”后面单开。顺便讲并查集适合维护什么关系之类的。