LeetCode 题解工作台
冗余连接
树可以看成是一个连通且 无环 的 无向 图。 给定一个图，该图从一棵 n 个节点 (节点值 1～n ) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ， edges[i] = [a i ,…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
根据题意，我们需要找到一条可以删去的边，删除后剩余部分是一个有着 个节点的树。我们可以遍历每一条边，判断这条边是否在同一个连通分量中。如果在同一个连通分量中，则说明这条边是多余的，可以删除，直接返回这条边即可。否则，我们将这条边所连接的两个节点合并到同一个连通分量中。 时间复杂度 $O(n \log n)$，空间复杂度 。其中 为边的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
树可以看成是一个连通且 无环 的 无向 图。
给定一个图，该图从一棵 n 个节点 (节点值 1～n) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
示例 1：
输入: edges = [[1,2], [1,3], [2,3]] 输出: [2,3]
示例 2：
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4]
提示:
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ai < bi <= edges.lengthai != biedges中无重复元素- 给定的图是连通的
解题思路
方法一：并查集
根据题意，我们需要找到一条可以删去的边，删除后剩余部分是一个有着 个节点的树。我们可以遍历每一条边，判断这条边是否在同一个连通分量中。如果在同一个连通分量中，则说明这条边是多余的，可以删除，直接返回这条边即可。否则，我们将这条边所连接的两个节点合并到同一个连通分量中。
时间复杂度 ，空间复杂度 。其中 为边的数量。
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(len(edges)))
for a, b in edges:
pa, pb = find(a - 1), find(b - 1)
if pa == pb:
return [a, b]
p[pa] = pb
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N \cdot \alpha(N)) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to efficiently detect cycles in a graph using DFS or Union Find.
- question_mark
Assess how well the candidate explains the significance of the cycle and redundant edge removal.
- question_mark
Evaluate their understanding of graph traversal and cycle detection trade-offs.
常见陷阱
外企场景- error
Misunderstanding the tree structure and treating the graph as fully connected without considering the cycle.
- error
Not recognizing the last added edge as the answer when multiple redundant edges exist.
- error
Incorrectly applying DFS or Union Find without careful tracking of visited nodes or sets.
进阶变体
外企场景- arrow_right_alt
Handle graphs with multiple cycles and determine which cycle's edge to remove.
- arrow_right_alt
Implement the solution using BFS instead of DFS or Union Find.
- arrow_right_alt
Extend the problem to handle undirected graphs with weighted edges.