数据结构与算法 / 系统课时
冗余边怎么快速识别
冗余边怎么快速识别
一张无向图持续加入边时,真正要判断的不是“这条边长什么样”,而是它两端是否已经连通。并查集能用近乎常数的代价维护连通关系,因此非常适合快速识别会形成环的冗余边。
学习目标
- 理解“加入边前已连通”为什么等价于“这条边会形成环”
- 用并查集实现冗余边检测并返回第一条冗余边
- 掌握路径压缩、按大小合并后的时间复杂度与适用边界
判断冗余边的本质
处理边 (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,该边就是冗余边。
复杂度和边界
设节点数为 、边数为 。路径压缩配合按大小合并后,每次 find 或 union 的摊还复杂度可写为 ,其中 是增长极慢的反阿克曼函数,因此扫描全部边约为 ,额外空间为 。
这种方法适合无向图的动态连通与环检测。如果问题要求输出具体环路径、处理有向图,或者删除边后仍需在线维护连通性,普通并查集就不够,需要换成 DFS、拓扑方法或更专门的动态连通结构。
按自己的节奏,确认真正理解。