冗余连接与环检测
对每条边执行合并操作，并检查两个节点是否已经连通，从而检测无向图中会形成环的边。
冗余连接与环检测 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是冗余连接
冗余连接问题（LeetCode 684）给定一棵包含 n 个节点的树和一条额外的边，这会恰好形成一个环。您的任务是找出移除后能够恢复树结构的那条边。如果存在多个答案，请返回输入列表中的最后一条。
包含 n 个节点的树恰好有 n-1 条边，并且连通且无环。再添加一条边就会恰好形成一个环。新增的（冗余）边连接了两个原本已经属于同一（same）连通分量的节点，这是 DSU 进行环检测的经典场景。
# Example
# n=5, edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
# Adding edge [2,3] creates cycle 1-2-3-1
# So [2,3] is the redundant connection
# Key insight: process edges one by one with DSU
# The FIRST edge where both endpoints are already connected is the redundant one
print('Tree property: n nodes, n-1 edges, no cycles')
print('Adding 1 edge: n nodes, n edges, exactly 1 cycle')
print('DSU approach: find the edge that connects already-connected nodes')使用 DSU 检测环
DSU 能够自然地检测环：在添加边 (u, v) 之前，检查 find(u) == find(v)。如果它们共享同一个根节点，就说明它们已经连通——添加这条边会形成环。这就是冗余边。
这种方法适用于无向图。对于每条边，我们要么成功对两个连通分量执行 union 操作（目前没有形成环），要么检测到两个端点已经属于同一（same）连通分量（发现环）。时间复杂度为 O(n × alpha(n))，近似为 O(n)。
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1)) # 1-indexed
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # same component => cycle found
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
print(find_redundant_connection(edges)) # [2, 3]算法执行过程
让我们逐步跟踪 [[1,2],[1,3],[2,3]]。开始时，每个节点都是自己的连通分量：{1}、{2}、{3}。
- 边 [1,2]：find(1)=1，find(2)=2，不同——对它们执行 union。连通分量：{1,2}、{3}
- 边 [1,3]：find(1)=根节点，find(3)=3，不同——对它们执行 union。连通分量：{1,2,3}
- 边 [2,3]：find(2)=根节点，find(3)=根节点——same 根节点！检测到环。返回 [2,3]。
该算法按顺序处理边，并返回第一条完成成环的边。由于题目保证只有一条额外的边，因此这始终是正确的冗余边。
def find_redundant_trace(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
print(f'Edge ({u},{v}): find({u})={pu}, find({v})={pv}', end=' => ')
if pu == pv:
print('CYCLE DETECTED!')
return [u, v]
parent[pv] = pu
print('merged')
return []
result = find_redundant_trace([[1,2],[1,3],[2,3]])
print('Redundant edge:', result)使用 DFS 检测无向图中的环
对于无向图中的环检测，DSU 的一种替代方法是带父节点跟踪的 DFS。在 DFS 过程中，如果我们到达一个已经访问过、且不是当前节点直接父节点的节点，就找到了回边——这表示存在环。
不过，DFS 方法需要 O(V + E) 的时间，并且只能返回是否存在环，不容易确定具体哪条边是冗余边。对于要求识别具体冗余边的问题，DSU 更受推荐，因为 union 失败时就能自然地找到该边。
from collections import defaultdict
def has_cycle_dfs(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb == parent:
continue # skip the edge we came from
if nb in visited:
return True # back edge => cycle
if dfs(nb, node):
return True
return False
for node in range(1, n + 1):
if node not in visited:
if dfs(node, -1):
return True
return False
print(has_cycle_dfs(3, [[1,2],[1,3],[2,3]])) # True
print(has_cycle_dfs(3, [[1,2],[1,3]])) # False有向图中的环检测
对于有向图，DSU 不能直接进行环检测，因为边具有方向。相反，应使用带三色标记的 DFS：白色（未访问）、灰色（位于当前 DFS 路径中）、黑色（已完全处理）。指向灰色节点的回边表示存在环。
在无向图中，任何回边都意味着存在环。在有向图中，指向黑色节点的跨边并不构成环——只有指向灰色节点的回边才构成环。这一区别非常关键，并且会在课程安排问题中进行测试。
def has_cycle_directed(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=white(unvisited), 1=grey(in stack), 2=black(done)
color = [0] * (n + 1)
def dfs(node):
color[node] = 1 # grey: currently visiting
for nb in graph[node]:
if color[nb] == 1:
return True # back edge to grey node => cycle
if color[nb] == 0:
if dfs(nb):
return True
color[node] = 2 # black: fully processed
return False
for node in range(1, n + 1):
if color[node] == 0:
if dfs(node):
return True
return False
from collections import defaultdict
print(has_cycle_directed(3, [[1,2],[2,3],[3,1]])) # True: 1->2->3->1
print(has_cycle_directed(3, [[1,2],[1,3],[2,3]])) # False冗余连接 II：有向图变体
LeetCode 685 将问题扩展到了有向图：每个节点恰好有一个父节点（形成一棵带一条额外边的有根树）。会出现两种情况：一个节点有两个父节点（入度为 2），或者存在一个环，但没有节点拥有两个父节点。
解决方案首先检查入度为 2 的节点。如果找到这样的节点，那么指向它的两条入边中必有一条是答案。然后通过 DSU 环检测确定应移除两条候选边中的哪一条。这种两阶段方法能够正确处理所有情况。
def find_redundant_directed(edges):
n = len(edges)
parent_map = {} # node -> its parent in the input
candidate1 = candidate2 = None
for u, v in edges:
if v in parent_map: # v already has a parent
candidate1 = [parent_map[v], v] # earlier edge
candidate2 = [u, v] # later edge
else:
parent_map[v] = u
# DSU cycle detection, skipping candidate2 if it exists
dsu = list(range(n + 1))
def find(x):
while dsu[x] != x: dsu[x] = dsu[dsu[x]]; x = dsu[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
dsu[px] = py; return True
for u, v in edges:
if candidate2 and [u, v] == candidate2: continue # skip candidate2
if not union(u, v): # cycle found without candidate2
return candidate1 if candidate1 else [u, v]
return candidate2 # no cycle when excluding candidate2 => candidate2 is redundant
print(find_redundant_directed([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_directed([[1,2],[2,3],[3,4],[4,1],[1,5]])) # [4,1]移除边后的图有效性
确定冗余边后，我们可以通过检查移除它是否会留下有效的树来验证结果：恰好 n-1 条边、所有节点连通且不存在环。对于面试题而言，DSU 会自然地保证这一点——如果我们返回 union 失败的那条边，移除它后就只剩下恰好 n-1 条成功执行 union 操作的边，而这些边会构成一棵生成树。
这正是 DSU 能够简洁解决此问题的原因：成功的 union 操作逐步构建树，而失败的 union 操作则找出不属于树的那条边。
def verify_tree(n, edges, removed_edge):
parent = list(range(n + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
components = n
for u, v in edges:
if [u, v] == removed_edge:
continue # skip the removed edge
pu, pv = find(u), find(v)
if pu == pv:
print('CYCLE DETECTED after removal! Wrong answer.')
return False
parent[pv] = pu
components -= 1
if components != 1:
print(f'Graph not connected ({components} components). Wrong answer.')
return False
print('Valid tree after removing edge:', removed_edge)
return True
edges = [[1,2],[1,3],[2,3]]
verify_tree(3, edges, [2,3])
verify_tree(3, edges, [1,2]) # wrong removal时间与空间复杂度分析
基于 DSU 的冗余连接解决方案会恰好处理每一条 n 条边一次，并且每次 union/find 操作的均摊代价为 O(alpha(n))。总时间复杂度为：O(n × alpha(n))，实际上为 O(n)。
空间复杂度为O(n)，用于存储父节点数组和秩数组。这已经是最优的——您至少必须读取全部 n 条边，并为每个节点存储一些状态。相比之下，朴素方法会在每次插入边后运行 DFS，时间复杂度为 O(n²)，空间复杂度为 O(n + E)。
# Summary of complexities
complexity = {
'Naive (DFS after each edge)': {'time': 'O(n^2)', 'space': 'O(n)'},
'DSU (path compression + rank)': {'time': 'O(n * alpha(n))', 'space': 'O(n)'},
'Sorting + DSU (Kruskal style)': {'time': 'O(n log n)', 'space': 'O(n)'},
}
for approach, costs in complexity.items():
print(f'{approach}:')
print(f' Time: {costs["time"]}')
print(f' Space: {costs["space"]}')
print()
print('alpha(n) <= 4 for all practical n, so DSU is effectively O(n).')边界情况：自环
自环边 [u, u] 会立即形成环，因为两个端点是同一个节点。在 DSU 中，find(u) == find(u) 始终为真，因此 union 会立即失败，并返回 [u, u] 作为冗余边。
大多数题目的约束都会保证不存在自环，但健壮的代码应当处理这种情况。DSU 的实现可以自然地处理它，无需任何特殊情况——环检查 if find(u) == find(v) 会在执行任何 union 操作之前捕获它。请始终使用单节点自环和最小规模输入等边界情况进行验证。
def find_redundant_robust(edges):
n = len(edges)
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return [u, v] # handles self-loops too: u==v => pu==pv always
parent[pv] = pu
return []
# Self-loop test
print(find_redundant_robust([[1,2],[2,2]])) # [2,2] self-loop
# Minimum tree test
print(find_redundant_robust([[1,2],[2,3],[1,3]])) # [1,3]
# Standard test
print(find_redundant_robust([[1,2],[1,3],[2,3],[2,4],[3,5]])) # [2,3]跨算法概括环检测
有多种算法可以检测环，每种算法都适用于不同的场景：
- DSU：无向图、在线接收边、每条边 O(alpha(n))——最适合统计环或查找冗余边
- 带父节点跟踪的 DFS：无向图、预先知道所有边、O(V+E)——最适合需要环路径的情况
- 三色 DFS：有向图、检测回边、O(V+E)——最适合课程安排和拓扑排序
- 拓扑 sort（卡恩算法）：有向图、通过剩余的非零入度节点检测环——最适合还需要排序的情况
# When to use which cycle-detection method:
# Problem type => preferred algorithm
problems = [
('Redundant Connection (undirected)', 'DSU'),
('Course Schedule (directed)', 'DFS three-color or Kahn topological sort'),
('Detect cycle in undirected graph', 'DFS with parent tracking or DSU'),
('Find cycle members in directed graph', 'DFS three-color + backtrack'),
('Online graph edges with cycle check', 'DSU'),
('Minimum spanning tree validity', 'DSU (Kruskal)'),
]
for problem, solution in problems:
print(f'{problem}\n => {solution}\n')包含边界情况的完整解法
下面是冗余连接问题的生产级解法，可处理所有边界情况：节点从 1 开始编号、恰好有一条冗余边，以及移除该边后会留下有效树这一保证。它使用带路径减半和按秩执行 union 操作的最优 DSU。
提交后，请思考后续问题：如果图中可能有多条冗余边，该怎么办？您需要跟踪所有形成环的边，并返回输入中的最后一条——相同（same）的贪心策略仍然有效，因为 DSU 会按顺序处理边。
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v]
return [] # should never reach here given valid input
test_cases = [
[[1,2],[1,3],[2,3]],
[[1,2],[2,3],[3,4],[1,4],[1,5]],
[[1,2],[1,3],[2,3],[2,4],[3,5]],
]
for tc in test_cases:
print(find_redundant_connection(tc))快速检查
请测试您对本课中“数据结构与算法——编程面试准备”概念的理解。
课程回顾
在本课中，您学到了：在无向图中，冗余连接是连接两个已经连通节点的边，DSU 会在 union 前检查 find(u) == find(v)，并返回该边来检测这种情况，以及有向图需要使用三色 DFS 或卡恩算法，而不是 DSU 来进行环检测。接下来，我们将把 DSU 应用于账户合并问题，其中电子邮件是节点，而账户之间的共享电子邮件会触发 union 操作。
常见问题解答
「冗余连接与环检测」课时是免费的吗？
是的 — 「冗余连接与环检测」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「冗余连接与环检测」这节课中我会学到什么？
对每条边执行合并操作，并检查两个节点是否已经连通，从而检测无向图中会形成环的边。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「冗余连接与环检测」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 带路径压缩的 DSU
- 按秩合并与反阿克曼函数界
- 冗余连接与环检测
- 账户合并与连通分量