并查集（DSU）中节点到集合代表的距离的意义与应用场景是什么

带权并查集「到代表元距离」的本质与应用 #

你看到的是带权并查集的基础实现，这里维护的「到根节点的距离」不是无意义的内部结构属性，是可以和实际业务中的「两点间相对关系/差值」直接对应的核心数据。普通并查集只能判断两个元素是否属于同一集合，带权并查集在此基础上还能快速计算同一集合内两个元素的相对关系，这就是它的核心价值。

距离的实际含义 #

你给出的示例代码中合并节点时默认将边权设为1，属于通用模板的简化写法，实际使用时这个边权可以根据具体问题的已知条件自定义，它代表两个节点之间的关系差值：

• 路径压缩时递归累加距离，本质是把当前节点到旧根的路径上的所有边权求和，得到当前节点到新根的直接关系值，避免后续重复遍历路径
• 同一集合内两个元素的相对关系，直接用两个元素各自到根的距离做运算即可得到

典型应用场景 #

这里举几个最容易理解的实际用例：

• 阵营判定问题：比如规则为「朋友的朋友是朋友，敌人的敌人是朋友」，我们可以约定距离模2为0代表和根是同阵营（朋友），模2为1代表是敌对阵营。判断两个人关系时，只要算两者到根的距离差模2的结果即可，合并两个阵营时根据两者的已知关系设置对应边权即可。
• 食物链问题：经典的三类生物捕食关系问题（A吃B、B吃C、C吃A），约定距离模3为0代表和根是同类，模3为1代表当前节点被根捕食，模3为2代表当前节点捕食根，就可以快速判断给出的捕食关系是否存在矛盾。
• 等差关系校验：如果给出多个形如a[x] - a[y] = k的条件，需要判断条件是否冲突、或者查询任意两个元素的差值，就可以用距离存储a[x]和根节点的差值，合并时根据已知的k值计算两个根之间的边权，查询时直接用两个节点到根的距离做差即可得到结果。
• 二分图判定：判定无向图是不是二分图时，用距离模2代表节点颜色，如果合并两个节点时发现二者已经在同一集合，且距离差模2为0，说明图中存在奇环，不是二分图。

简易可视化示例 #

以你给出的固定边权为1的代码为例，操作过程的距离变化如下：

1. 执行make_set(1)、make_set(2)、make_set(3)：每个节点的父节点是自身，到根距离都是0
2. 执行union_sets(1,2)：将2的根（节点2）挂到1的根（节点1）下，设置2到1的边权为1，此时find_set(2)返回(1, 1)，代表2属于根为1的集合，到根距离为1
3. 执行union_sets(2,3)：先查到2的根是1，3的根是3，将3的根挂到1下，设置边权为1，此时find_set(3)会递归计算得到到根1的距离为2，也就是3和1的距离差为2

内容的提问来源于stack exchange，提问作者manu