DeepSeek LeetCode 1489.找到最小生成树里的关键边和伪关键边 public List＜List＜Integer＞＞ findCriticalAndPseudoCritical

本题要求找出无向加权图中所有最小生成树（MST）的关键边和伪关键边。关键边出现在所有MST中，伪关键边出现在某些但非全部MST中。

算法思路

1. 计算原图的最小生成树权重
使用Kruskal算法（并查集）求出任意一个MST的总权重 originalWeight。
2. 逐边判断
对每条边 i：
· 关键边判断：忽略该边，计算剩余图的MST权重。若结果大于 originalWeight 或图不连通，说明该边必须存在于所有MST中，即为关键边。
· 伪关键边判断：若非关键边，则强制将该边加入图中，再计算MST。若得到的权重等于 originalWeight，说明该边可以出现在某个MST中，即为伪关键边。
3. 返回结果
关键边索引列表和伪关键边索引列表。

复杂度分析

· 时间复杂度：O(E²·α(V))，其中 E ≤ 200，V ≤ 100，可以接受。
· 空间复杂度：O(E + V)。

Java代码

```java
import java.util.*;

class Solution {
class Edge implements Comparable<Edge> {
int u, v, weight, idx;
Edge(int u, int v, int weight, int idx) {
this.u = u; this.v = v; this.weight = weight; this.idx = idx;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}

public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
int m = edges.length;
List<Edge> edgeList = new ArrayList<>();
for (int i = 0; i < m; i++) {
edgeList.add(new Edge(edges[i][0], edges[i][1], edges[i][2], i));
}
// 按权重排序，后续每次MST计算使用这个排序列表
Collections.sort(edgeList);

int originalWeight = kruskal(n, edgeList, -1, -1);

List<Integer> critical = new ArrayList<>();
List<Integer> pseudo = new ArrayList<>();

for (int i = 0; i < m; i++) {
// 忽略边i，判断是否为关键边
int weightWithout = kruskal(n, edgeList, i, -1);
if (weightWithout > originalWeight) {
critical.add(i);
continue;
}
// 强制包含边i，判断是否为伪关键边
int weightWith = kruskal(n, edgeList, -1, i);
if (weightWith == originalWeight) {
pseudo.add(i);
}
}

return Arrays.asList(critical, pseudo);
}

private int kruskal(int n, List<Edge> edges, int skipIdx, int forceIdx) {
UnionFind uf = new UnionFind(n);
int totalWeight = 0;
int edgeCount = 0;

// 强制包含某条边
if (forceIdx != -1) {
Edge e = null;
for (Edge edge : edges) {
if (edge.idx == forceIdx) {
e = edge;
break;
}
}
// 如果两端已连通，则无法形成MST
if (!uf.union(e.u, e.v)) {
return Integer.MAX_VALUE;
}
totalWeight += e.weight;
edgeCount++;
}

// 正常Kruskal
for (Edge e : edges) {
if (e.idx == skipIdx || e.idx == forceIdx) continue;
if (uf.union(e.u, e.v)) {
totalWeight += e.weight;
edgeCount++;
if (edgeCount == n - 1) break;
}
}

return edgeCount == n - 1 ? totalWeight : Integer.MAX_VALUE;
}

class UnionFind {
int[] parent, 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) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false;
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; }
return true;
}
}
}
```