并查集（union find）

[WeiShengv99]

并查集（union find）数据结构学习记录

动态连通性 （Dynamic connectivity）

如下图。我们给了几个数字 数字之间是否相连来判断是否是同一个集合 ， 下图就只有2个集合

进阶的使用，可以用来判断 p 和 q点是否相连

[WeiShengv99]

Quick find

我们利用 小标表示当前的数字，值来表示所属于的集合,一开始每个值都是一个单独的集合

如果我们想要将2个集合相连，那么只需要把2个集合对应的值都改成 统一的值就行了，图中 0 5 6 都是 0 的集合 1 2 7 都是 1的集合。 （当然你在相连集合的时候 应该变成 值 A 还是B 是需要进行考虑的，涉及到性能）

图中 0 5 6 都是 0 的集合 1 2 7 都是 1的集合，
只要实现了这种数据结构，那么我们可以非常方便的查询是否是在一个集合， 例如查询 5 6 是否是一个集合，那么只需要判断 他们的值是否相等即可。

[WeiShengv99]

Quick union【lazy approach】

我们可以发先 上面的实现方式很容易去查找 是否属于同一个集合，但是当我们相连n个集合的时候，需要遍历n次整个数组，这个操作是很巨大的。我们需要优化。

我们采用新的结构来表达，类似与树的模式

例如 2的父节点应该是 9 那么 2号位置的值就是 9，3号位置的父节点应该是 4 ，那么值就是4

这样，我们去检查是否在一个集合，只需要查看root节点是否相同。同时我们去merge集合的时候，只需要将2个树的root进行merge即可

但是，这种结构任然有缺点，树可能是一条直线 ，非常非常的深，那么我们回溯root的时候非常耗时。

那么我们需要避免构成一个tall tree，利用 树重 的概念来进行优化。（当前树拥有多少节点）

我们避免 让高的树 成为矮的树的子树，这样会让树变高，应该让矮的树当高的树的子树

同时我们还可以在 回溯root的时候，去优化我们目前拥有的树，将path上经过的所有结点直接链接到根节点，压平当前的路径。

扩展一下： 还有rank的方式去进行优化，这种方式可以进一步避免tall tree的形成。

合并优化二：按秩合并
按秩合并给每个元素纪录了一个秩（rank），代表着以这个元素为根的树的高度的上限 (upper bound for its height)。最开始，每个元素的秩都是0。当合并两棵树时，对比他们的秩，秩较大的那棵树的根将作为另一个根的父亲，新父亲根的秩增加一

[WeiShengv99]

总结一下时间复杂度

[WeiShengv99]

实际应用

进阶的使用，可以用来判断 p 和 q点是否相连

我们还记得当初的union find 的应用。常见的类似说 在一张图片中 标记相连的区域。

参考资料

https://www.bilibili.com/video/BV1u441127b5/?p=5