并查集

前言

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

正文

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

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

本文《并查集》由 RM Olive (rmolives@gmail.com) 发布,如有版权纠纷及其他问题可以与我取得联系进行解决。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇