LeetCode 1489. 找到最小生成树里的关键边和伪关键边
题目描述
题意分析
给定连通无向加权图，最小生成树用
n - 1条边连接全部节点且总权重最小。图中可能有多棵权重相同的最小生成树，需要区分两类边。关键边必须出现在每一棵最小生成树中；伪关键边能出现在某些最小生成树中，但也存在不选它的最小生成树。既不可能参与最小生成树的边不属于两类。分别返回原始输入中的边编号，而非排序后位置。
解法：Kruskal 枚举每条边
核心思路
[!blue]
先用 Kruskal 求没有附加限制时的最小总权重
base。Kruskal 按权重从小到大取边，仅在两个端点属于不同连通分量时合并：这样不会形成环，而连接当前不同分量的最小可用边能由生成树的交换性质安全选入。成功合并n - 1次就得到生成树。对每条边先做排除实验。如果禁止使用它后图无法连通，说明任何生成树都离不开它；如果仍能连通但最小权重超过
base，说明不用它就无法达到最优。两种情况都等价于它必须出现在全部最小生成树中，因此是关键边。若排除后仍能达到
base，已经知道存在不选它的最小生成树，再判断是否也能选它。强制先把该边加入，合并两个端点并计入权重，然后按权重顺序补选其余边。可以把这次合并看作缩成一个节点，后续 Kruskal 求的就是所有包含该边的生成树中的最小权重。强制后的最小权重若等于
base，就证明既有包含它、也有不包含它的最优树，所以是伪关键边；若更大，则它不能属于任何最小生成树。每次实验的连通状态独立，必须重新创建并查集。禁止边、强制边都在后续扫描中跳过；构造结束若合并数不足
n - 1，返回无穷大而不是部分权重。排序前为每条边保存原始编号，最后按这个编号输出。
解题步骤
- 为每条边附加原始编号，按权重升序排序。
- 不禁用、不强制任何边，运行一次 Kruskal 得到基准权重。
- 对当前边，重建并查集并排除它；若无法连通或权重变大，记为关键边。
- 否则再重建并查集，先选当前边再补齐生成树；权重等于基准时记为伪关键边。
- 返回两个原始编号列表。
代码实现
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+1)+EV+E^2\alpha(V))$，其中 $V$、$E$ 是节点数和边数。边排序一次，每条边至多进行两次构造；每次初始化并查集为 $O(V)$，扫描合并为 $O(E\alpha(V))$。
- 空间复杂度：$O(E+V)$，用于带原编号的边数组、结果列表与每次重建的并查集。
关键点总结
[!green]
- 排除后不能最优，证明边必选；强制后仍然最优，证明边可选。
- 先排除判关键，再强制判伪关键，保证两类不重复。
- 强制边先连接端点，相当于缩点后继续求最优补全。
- 每次实验必须形成完整生成树，部分权重不能与基准比较。
易错点总结
[!yellow]
- 某一次 Kruskal 选中一条边，只说明它能参与某棵最优树，不能说明它在所有最优树中必选。
- 实验间复用并查集，会继承此前连通关系，破坏独立限制条件。
- 强制边只加权重却不先合并端点，后续可能重复连通并形成环。
- 强制边在后续扫描中还要跳过，避免被重复处理。
- 图不连通时返回部分权重，会把不完整的森林误认为比生成树更便宜。
- 排序下标仅用于这次实验，最终必须返回事先保存的原始边编号。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1135. 最低成本连通所有城市 | 中等 | 先求最小生成树基准，再通过禁用或强制加入某条边判断它对最优成本的影响。 |
| 1192. 查找集群内的关键连接 | 困难 | 桥体现连接必需性，本题还受权重影响；同权候选缩图中的桥可用于识别关键边。 |
| 补充题 209. 最小生成树总权重 | 中等 | 都用 Kruskal 构造最小生成树；本题还要分别强制或排除边来判定关键性。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！