本篇对应源码见仓库
solutions/xcpc/algorithm/graph/dsu/。
并查集的变式通常是在基本操作（find和merge）上，加入了额外的逻辑或应用场景。
1. 维护额外信息（带权并查集/维护属性的并查集）
要求不仅要处理连通性，还有更新或维护集合想换的某种属性
题目关键词
连通块大小、统计、求和、最值、相对大小、相对距离、奇偶性关系、传递性。
核心思想
在 merge 时，除了连接父节点，还需要根据题目要求将一个集合的属性“转移”或者“合并”到另一个集合的根阶段上。路径压缩时也需要进行同步更新。
常见属性
集合大小
放入 size 操作即可
集合内元素的和/积/最大值/最小值
如合并两个集合时，将他们的元素和累加到新的根节点上
连通块数量
方法一：
先记录初始状态下总的连通块数量，然后每次成功 merge 时连通块数量就减一
方法二：
操作结束后，将所有元素的跟放入 set 中
到根节点的距离/相对值
例如，用 d[i] 表示 i 到 fa[i] 的某种权值，在路径压缩时就需要累加这些权值。
通常用来表示元素之间的相对关系（如 比 大多少，或者离多远）
2. 逆向思维
有些问题会出现进行“删除”操作，而并查集擅长的是合并，而不能高效的拆分，这时可以考虑将操作逆序处理
题目关键词
边的删除、点的删除、离线处理、撤销操作
核心思想
- 首先记录所有操作
- 确定所有操作后的最终状态，哪些元素是连通的，这个状态就是初始化状态
- 处理操作：将操作序列逆序，从后往前处理操作，原来是“删除”操作的，就进行“添加”，原来是“查询”则继续“查询”
3. 种类并查集（扩展域并查集）
当元素之间存在多种相互关系（而不仅仅是简单的相连通关系），或者关系具有传递性且需要判断不同类型的关系时，就需要使用种类并查集。
题目关键词
朋友、敌人、同类、异类、食物链、捕食、对抗、关系判断。
核心思想
为每个原始元素 i ，创建多个“分身”或“状态”，例如 i 、i + N 、i + 2N 等。每个分身代表 i 在某种特定关系下的状态 。
i可能代表自己，或者同类关系i + N可能代表与i处于某种特定关系的对象集合（例如i的敌人，猎物）i + 2N可能代表其他另一种关系对象集合
4. 与图论结合
并查集在图论应用非常广泛，因为它天然适合处理连通性问题。
题目关键词
连通分量、环、最小生成树、二分图、加边
核心思想
图论的节点就是并查集的元素，边就是合并的依据。
判断图的连通性
如判断两点是否连通，或者计算连通块数量
最小生成树算法（Kruskal）
通过并查集来判断新加入的边是否会构成环
环检测
在添加新的边时，如果两个节点原本已经在同一个集合中，那么添加新的边后就会形成环
二分图判断
可以使用并查集来判断图是否为二分图（与种类并查集有异曲同工之妙，可以维护一个点到根的距离的奇偶性来判断）。