如何使用union-find（并查集）解决管理关系设置与查询问题

很多资料推荐用并查集实现的核心原因是，该需求的核心是维护节点的父级映射关系，和并查集的核心存储结构完全匹配。我们不需要传统并查集的路径压缩优化，因为路径压缩会破坏原始的父子层级关系，无法准确查询完整管理链。这里的并查集变体仅维护每个节点的直接父节点，所有操作的时间复杂度取决于管理链的长度，实际场景中层级深度不会过大，效率远高于多叉树遍历方案。

接口实现逻辑 #

• setManager(A, B)：直接将B的父节点设为A即可，符合「每个人仅1名直接上级」的约束
• setPeer(A, B)：将B的父节点设为A的父节点即可，操作后两者共享同一个直接上级
• query(A, B)：从B出发向上遍历父节点，直到到达根节点，遍历过程中如果遇到A则返回True，遍历完所有上级都没遇到则返回False

完整代码实现（Python示例） #

class HierarchyUF:
    def __init__(self):
        # 存储每个员工的直接上级，key为员工id，value为上级id
        self.parent = {}
    
    def setManager(self, A, B):
        # 自动初始化未录入的员工
        if A not in self.parent:
            self.parent[A] = None
        if B not in self.parent:
            self.parent[B] = None
        # 将A设为B的直接上级
        self.parent[B] = A
    
    def setPeer(self, A, B):
        # 自动初始化未录入的员工
        if A not in self.parent:
            self.parent[A] = None
        if B not in self.parent:
            self.parent[B] = None
        # A没有上级的情况，B也同步设为无上级
        a_manager = self.parent[A]
        self.parent[B] = a_manager
    
    def query(self, A, B):
        # 边界判断：A或B不在系统中直接返回False
        if A not in self.parent or B not in self.parent:
            return False
        # 从B开始向上遍历管理链
        current = B
        while current is not None:
            if current == A:
                return True
            current = self.parent[current]
        return False

测试用例示例 #

# 测试示例
uf = HierarchyUF()
# 设置张三是李四的上级
uf.setManager("张三", "李四")
# 设置王五是李四的平级
uf.setPeer("李四", "王五")

print(uf.query("张三", "王五")) # 输出True，张三在王五的管理链中
print(uf.query("李四", "王五")) # 输出False，李四不是王五的上级
print(uf.query("王五", "张三")) # 输出False，王五不在张三的管理链中

效率说明 #

• 前两个操作setManager和setPeer都是*O(1)*时间复杂度，直接修改父节点映射即可
• 查询操作query的时间复杂度为O(k)，k为B的管理链长度，企业实际场景中层级普遍在10层以内，效率远高于多叉树全局遍历的方案
  如果需要进一步优化查询效率，可以额外维护每个节点的祖先集合，每次修改父节点的时候同步更新，但会牺牲一点写入性能，可根据业务读写比例选择。

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