数据结构与算法 / 系统课时

冗余边怎么快速识别

冗余边怎么快速识别

一张无向图持续加入边时,真正要判断的不是“这条边长什么样”,而是它两端是否已经连通。并查集能用近乎常数的代价维护连通关系,因此非常适合快速识别会形成环的冗余边。

学习目标

  • 理解“加入边前已连通”为什么等价于“这条边会形成环”
  • 用并查集实现冗余边检测并返回第一条冗余边
  • 掌握路径压缩、按大小合并后的时间复杂度与适用边界

判断冗余边的本质

处理边 (u, v) 时,先查询 u 和 v 的根节点。如果根不同,说明它们属于两个连通分量,这条边用于连接两个分量,不冗余;如果根相同,说明当前图中已经存在一条从 u 到 v 的路径,再加入 (u, v) 就会闭合成环。

并查集识别冗余边流程

这个判断只依赖“加入当前边之前”的连通状态,因此边要按题目给定顺序处理。并查集并不会保存完整路径,它只维护每个节点所属的连通分量,这正是本问题需要的信息。

用并查集完成检测

下面示例返回输入顺序中第一条冗余边。find 使用路径压缩,union 按集合大小合并,避免父节点链退化。

python
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            # 路径压缩:后续查询直接靠近根节点。
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        # 小集合挂到大集合上,控制树高。
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

def find_redundant_edge(edges: list[list[int]]) -> list[int]:
    n = max(max(u, v) for u, v in edges)
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]
    return []

if __name__ == "__main__":
    edges = [[1, 2], [1, 3], [2, 3]]
    print(find_redundant_edge(edges))

预期输出

text
[2, 3]

前两条边把 1、2、3 连成一个连通分量;处理 [2, 3] 时,两端根节点已经相同,所以 union 返回 False,该边就是冗余边。

复杂度和边界

设节点数为 VV、边数为 EE。路径压缩配合按大小合并后,每次 find 或 union 的摊还复杂度可写为 O(α(V))O(\alpha(V)),其中 α\alpha 是增长极慢的反阿克曼函数,因此扫描全部边约为 O(Eα(V))O(E\alpha(V)),额外空间为 O(V)O(V)。

这种方法适合无向图的动态连通与环检测。如果问题要求输出具体环路径、处理有向图,或者删除边后仍需在线维护连通性,普通并查集就不够,需要换成 DFS、拓扑方法或更专门的动态连通结构。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

冗余边怎么快速识别

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通