LeetCode 题解工作台
找到最小生成树里的关键边和伪关键边
给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [from i , to i , weight i ] 表示在 from i 和 to i 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 并查集
答案摘要
先利用 Kruskal 算法，得出最小生成树的权值 v。然后依次枚举每条边，按上面的方法，判断是否是关键边；如果不是关键边，再判断是否是伪关键边。 class UnionFind:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 并查集 题型思路
题目描述
给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。
请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。
请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。
示例 1：
输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]] 输出：[[0,1],[2,3,4,5]] 解释：上图描述了给定图。 下图是所有的最小生成树。注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。 边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。
示例 2 ：
输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]] 输出：[[],[0,1,2,3]] 解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。
提示：
2 <= n <= 1001 <= edges.length <= min(200, n * (n - 1) / 2)edges[i].length == 30 <= fromi < toi < n1 <= weighti <= 1000- 所有
(fromi, toi)数对都是互不相同的。
解题思路
方法一：Kruskal 算法
先利用 Kruskal 算法，得出最小生成树的权值 v。然后依次枚举每条边，按上面的方法，判断是否是关键边；如果不是关键边，再判断是否是伪关键边。
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.n = n
def union(self, a, b):
if self.find(a) == self.find(b):
return False
self.p[self.find(a)] = self.find(b)
self.n -= 1
return True
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
class Solution:
def findCriticalAndPseudoCriticalEdges(
self, n: int, edges: List[List[int]]
) -> List[List[int]]:
for i, e in enumerate(edges):
e.append(i)
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
v = sum(w for f, t, w, _ in edges if uf.union(f, t))
ans = [[], []]
for f, t, w, i in edges:
uf = UnionFind(n)
k = sum(z for x, y, z, j in edges if j != i and uf.union(x, y))
if uf.n > 1 or (uf.n == 1 and k > v):
ans[0].append(i)
continue
uf = UnionFind(n)
uf.union(f, t)
k = w + sum(z for x, y, z, j in edges if j != i and uf.union(x, y))
if k == v:
ans[1].append(i)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on sorting edges O(E log E) and running Union Find operations for each edge O(E * α(n)) where α is the inverse Ackermann function, yielding roughly O(E log E + E * α(n)). Space complexity is O(n + E) for Union Find parent and rank arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Using Union Find plus Kruskal is expected to compute MST efficiently.
- question_mark
Checking MST weight changes when removing edges indicates criticality understanding.
- question_mark
Forcing edges in MST tests pseudo-critical behavior and optional inclusion reasoning.
常见陷阱
外企场景- error
Failing to sort edges before applying Union Find can give incorrect MST weight.
- error
Not restoring Union Find state correctly between tests may misclassify edges.
- error
Confusing critical with pseudo-critical edges due to MST weight comparison errors.
进阶变体
外企场景- arrow_right_alt
Determine all edges that appear in any MST of a graph, regardless of weight uniqueness.
- arrow_right_alt
Count the number of distinct MSTs in a weighted graph using Union Find plus combinatorial checks.
- arrow_right_alt
Find critical edges in a directed weighted graph where minimum spanning arborescence is required.