带权并查集(Weighted Union-Find)

带权并查集(Weighted Union-Find),又称带权值的并查集,是在经典并查集基础上为每个节点附加一个到父节点权值的扩展结构。它不仅能回答两个元素是否属于同一集合,还能在它们同属一个集合时,推断出二者之间的相对关系或差值。

概述

普通并查集只维护元素的分组信息,回答连通性问题。但许多实际问题除了要知道两元素是否相关,还需要知道它们之间量化的相对关系,例如甲比乙重多少、某物属于哪一类。带权并查集通过在指向父节点的边上附加权值来编码这种关系。

核心原理

结构为每个节点维护一个数组,记录它到父节点的权值(通常表示与父节点的差值或某种模关系)。带权并查集的关键在于路径压缩和合并时对权值的正确累加与更新。

• 查找:在路径压缩把节点直接挂到根上的同时,累加沿途所有边权,得到该节点到根的权值。
• 合并:连接两棵树的根时,需根据待合并两元素之间的已知关系,推算出新连边应赋予的权值,保证一致性。
• 查询关系:若两元素同根,则它们的相对关系等于各自到根权值之差。

应用场景

带权并查集适合处理一类带相对约束的合并查询问题,例如食物链等种类关系判定(权值取模三表示三种类别的循环关系)、货物称重的相对重量推断、以及某些差分约束系统的在线判定。它的时间复杂度与普通并查集相同,近乎常数。

常见问题

问:带权并查集和普通并查集的复杂度一样吗?答:一样。配合路径压缩与按秩合并,单次操作的摊还复杂度仍接近常数,权值维护只是常数倍的额外计算。

问:权值一定是差值吗?答:不一定。权值可以是差值、模某数的余数,或满足结合律的任意关系,具体取决于问题;关键是查找与合并时要按对应的运算法则正确累加。