一、基础
初始化：最开始，每个元素各自为战，没有从属关系，因此将其所属（父结点）标为自己。
查询：用递归的方法来实现对代表元素的查询，逐层访问父结点，直至根结点。判断两个元素是否同属一个集合，只需判断二者根结点是否相同。
合并：先找到两个集合的根，然后将前者的父结点设为后者即可，反之亦然。
二、路径压缩
如果每一次都合并都针对子结点，那么每次想找到这个子结点的根都需要遍历其所有的父辈，此时遍历的就是一条长长的链表，因此需要进行路径压缩。
路径压缩：把沿途每个结点的父结点都设为根结点。
查询：路径压缩版
一行版：
三、按秩合并
假设将一棵树的根与一个单独结点进行合并，那么有两种合并方式：
- 将单独结点作为根的子结点；
- 将单独结点作为根的父结点；
由于第二种方式会使得合并后树的深度变大，所有这种方式有缺陷，故应选择第一种方式。
按秩合并：用一个 rank 数组记录每个结点作为根结点所对应树的深度，一开始所有元素的秩设为 1 ，合并时将秩小的结点作为秩大的结点的子结点。
路径压缩与按秩合并一起使用可使时间复杂度接近 ，但可能会破坏秩的准确性，因此建议使用路径压缩版本。
初始化：按秩合并
合并：按秩合并
参考文献
[1] 算法学习笔记(1) : 并查集
原创存证 · 本地哈希 · af09569bacae...
算法:SHA-256
时间:2026-10-21
哈希:
af09569bacae1372a9860b28647b097f7b8ccfbca7a4ddea2c940beb5ca428cf该信息用于辅助证明当前内容版本，不等同于法律公证或版权登记。
- 作者:BeZer0
- 链接:https://blog.bezer0.cn/postgrad/3ff0bc13-b7ac-8066-8e5c-fdd7af64d271
- 声明:本文为原创文章，采用 CC BY-NC-SA 4.0 协议，转载请注明作者和原文链接。
