LeetCode 1489. 找到最小生成树里的关键边和伪关键边
目录
题目描述
题意分析
给一张
n个点、带权无向连通图，要把每条边分成三类并输出前两类的原始下标：
- 关键边：删掉它之后，图的最小生成树权重会变大（或者图直接不连通）。等价说法是「它出现在每一棵最小生成树里」。
- 伪关键边：不是关键边，但至少存在一棵最小生成树包含它。
- 剩下的边：任何一棵最小生成树都不会用到它。
这两个定义本身就把解法写出来了——它们都是「反事实」的判断，一个问「拿掉会怎样」，一个问「强行加上会怎样」。只要能反复计算最小生成树的权重，两个判定就都是一次比较。
约束是本题最重要的信号：
n <= 100，边数edges.length <= 200。这个规模小得反常。$E$ 只有 200，意味着「对每条边各跑两次 Kruskal」的 $O(E^2 \alpha)$ 也不过 $200 \times 200 \times 2 = 8 \times 10^4$ 次并查集操作，毫无压力。出题人给出这个范围，就是在明示「暴力枚举每条边 + 重跑 MST」是期望解法；真正需要证明的是「删边变大 ⇒ 关键边」和「强制加入仍等于基准 ⇒ 伪关键边」这两条判据的正确性，而不是把 Tarjan 求桥那套搬出来。
有一个陷阱必须提前处理：题目要返回原始下标，而 Kruskal 必须先按权重排序。排序会打乱下标，所以排序前必须把原始下标随边一起带上。
边界：可能存在权重相同的多条边（这正是「伪关键」这个概念存在的根本原因——权重相同的边可以互换，谁进 MST 都行）；可能存在重边和权重相同的平行结构；删掉某条边后图可能不连通，此时该边必然是关键边。
解法：Kruskal 枚举每条边
核心思路
数据规模允许对每条边重新运行 Kruskal。先用全部边求最小生成树权重
base，再通过“排除”和“强制”两个反事实实验分类。
- 排除边 e 后，若图不连通或最小权重大于
base，说明每棵 MST 都必须包含 e，它是关键边。- 对非关键边，先强制加入 e，再用 Kruskal 补齐；若总权重仍等于
base，说明至少存在一棵包含 e 的 MST，它是伪关键边。必须先判关键边，因为关键边被强制加入时也会得到
base。排序前给每条边附加原始下标，避免 Kruskal 排序后丢失题目要求的编号。
buildMst(skip, force)每次使用全新的并查集。强制边先合并并计入权重；随后按权重升序扫描其余边，只在连接两个不同分量时选择。若最终选择边数不足n - 1，返回无穷大表示不连通。正确性说明：Kruskal 的割性质保证
buildMst分别得到无约束、排除某边、包含某边这三种约束下的最小权重。因此排除后变差恰好等价于“所有 MST 都含该边”；排除不变而强制后仍为base，恰好等价于“存在但并非所有 MST 含该边”。两类互斥且与定义一致。
解题步骤
- 将每条边扩展为
[u,v,weight,originalIndex]，按权重排序一次。- 实现受
skip、force约束的 Kruskal，并用n - 1次成功合并判断连通。- 无约束运行一次得到
base。- 对每条排序后的边，先排除运行；结果大于
base就加入关键边。- 否则强制运行；结果等于
base就加入伪关键边。- 输出两个原始下标列表。
官方样例的基准权重为 7；排除原始边 0、1 后最优权重升为 8，所以它们关键。边 2、3、4、5 都可被强制加入且仍得到 7，因此是伪关键边。权重相同、平行边以及排除后断图都由同一流程处理。
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
private static final long INF = Long.MAX_VALUE / 4;
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(
int n, int[][] edges) {
int[][] sorted = new int[edges.length][4];
for (int i = 0; i < edges.length; i++) {
sorted[i] = new int[] {
edges[i][0], edges[i][1], edges[i][2], i
};
}
Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2]));
long base = buildMst(n, sorted, -1, -1);
List<Integer> critical = new ArrayList<>();
List<Integer> pseudoCritical = new ArrayList<>();
for (int i = 0; i < sorted.length; i++) {
if (buildMst(n, sorted, i, -1) > base) {
critical.add(sorted[i][3]);
} else if (buildMst(n, sorted, -1, i) == base) {
pseudoCritical.add(sorted[i][3]);
}
}
return Arrays.asList(critical, pseudoCritical);
}
private long buildMst(int n, int[][] edges, int skip, int force) {
UnionFind unionFind = new UnionFind(n);
long weight = 0;
int used = 0;
if (force >= 0) {
int[] edge = edges[force];
if (!unionFind.union(edge[0], edge[1])) {
return INF;
}
weight += edge[2];
used++;
}
for (int i = 0; i < edges.length && used < n - 1; i++) {
if (i == skip || i == force) {
continue;
}
int[] edge = edges[i];
if (unionFind.union(edge[0], edge[1])) {
weight += edge[2];
used++;
}
}
return used == n - 1 ? weight : INF;
}
private static class UnionFind {
private final int[] parent;
private final int[] rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return false;
}
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
}
import "sort"
func findCriticalAndPseudoCriticalEdges(n int, edges [][]int) [][]int {
sorted := make([][]int, len(edges))
for i, edge := range edges {
sorted[i] = []int{edge[0], edge[1], edge[2], i}
}
sort.Slice(sorted, func(i, j int) bool {
return sorted[i][2] < sorted[j][2]
})
const inf int64 = 1 << 60
buildMst := func(skip, force int) int64 {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
find := func(x int) int {
for x != parent[x] {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
union := func(x, y int) bool {
rootX, rootY := find(x), find(y)
if rootX == rootY {
return false
}
if rank[rootX] < rank[rootY] {
parent[rootX] = rootY
} else if rank[rootX] > rank[rootY] {
parent[rootY] = rootX
} else {
parent[rootY] = rootX
rank[rootX]++
}
return true
}
var weight int64
used := 0
if force >= 0 {
edge := sorted[force]
if !union(edge[0], edge[1]) {
return inf
}
weight += int64(edge[2])
used++
}
for i, edge := range sorted {
if used == n-1 {
break
}
if i == skip || i == force {
continue
}
if union(edge[0], edge[1]) {
weight += int64(edge[2])
used++
}
}
if used != n-1 {
return inf
}
return weight
}
base := buildMst(-1, -1)
critical := make([]int, 0)
pseudoCritical := make([]int, 0)
for i, edge := range sorted {
if buildMst(i, -1) > base {
critical = append(critical, edge[3])
} else if buildMst(-1, i) == base {
pseudoCritical = append(pseudoCritical, edge[3])
}
}
return [][]int{critical, pseudoCritical}
}
复杂度分析
- 时间复杂度：$O(E \log E + E^2 \alpha(V))$。排序一次；每条边最多触发两次扫描全部边的 Kruskal。
- 空间复杂度：$O(E + V)$。排序副本占 E，并查集占 V；输出不计入额外空间。
关键点总结
- 关键边用“排除后是否变差”判定，伪关键边用“强制后能否仍最优”判定。
- 必须先关键、后伪关键，保证两个输出列表互斥。
- 每轮 Kruskal 都要重建并查集，避免状态泄漏。
- 排序前绑定原始下标；所有分类结果都返回原始编号。
- 不连通统一编码为无穷大，使断图和权重上升共用同一比较。
易错点总结
- 先判伪关键：关键边强制加入也等于
base，会同时出现在两个列表。- 排除后不检查连通性：桥边被删后只得到一片森林，其较小权重不能与 MST 比较。
- 强制加入但漏加边权或边数：受约束 Kruskal 的结果会系统性偏小或被误判为不连通。
- 主循环再次选择强制边：若实现不依赖并查集自动拒绝，会重复计数；代码显式跳过
force。- 复用并查集：上一轮连通状态会污染下一条边的分类。
- 丢失原始下标：排序位置不是题目要求的边编号。
- 关键判断使用
>=：排除后权重相等代表存在不含该边的 MST，它不是关键边。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1584. 连接所有点的最小费用 | 中等 | 边由坐标两两生成的稠密图，考察 Kruskal 与 Prim 在稠密图上的取舍 |
| 1135. 最低成本连通所有城市 | 中等 | 最裸的 MST 模板，重点在判断图是否连通、不连通时返回 -1 |
| 1168. 水资源分配优化 | 困难 | 需要引入虚拟节点把「打井成本」建模成边，考察建图技巧而非算法本身 |
| 1319. 连通网络的操作次数 | 中等 | 只用并查集数连通块与冗余边，不涉及权重，是本题并查集部分的简化版 |
| 684. 冗余连接 | 中等 | 用并查集在加边过程中检测出第一条成环的边，考察 union 返回值的用法 |
| 721. 账户合并 | 中等 | 并查集配合哈希映射把字符串归组，重点在如何把非整数实体映射成并查集下标 |