Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree hard
Description
Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph’s edges that connects all vertices without cycles and with the minimum possible total edge weight.
Find all the critical and pseudo-critical edges in the given graph’s minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is an edge that can appear in some MSTs but not all.
Note that you can return the indices of the edges in any order.
Examples
> Case 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]]
Output: [[0,1],[2,3,4,5]]
> Case 2:
n = 4, edges = [[0,1,1],[1,2,1],[0,2,1],[2,3,1]]
Output: [[3],[0,1,2]]Constraints
2 <= n <= 1001 <= edges.length <= min(200, n*(n-1)/2)edges[i].length == 30 <= ai < bi < n1 <= weighti <= 1000- All pairs
(ai, bi)are distinct.
State design / Intuition
Definitions:
- Critical edge: removing it from the graph increases the MST weight (or disconnects the graph).
- Pseudo-critical edge: it appears in some MST but not all — forcing it in gives the same MST weight, but skipping it still allows a valid MST.
Algorithm:
For each edge i, run two experiments with Kruskal’s as the subroutine:
- Skip test: Run Kruskal’s on all edges except i. If the resulting weight > base MST weight (or the graph is disconnected), edge i is critical.
- Force test: Force edge i into the MST (add it first, then run Kruskal’s on the rest). If the resulting weight == base MST weight, edge i is pseudo-critical.
Key: An edge cannot be both critical and pseudo-critical. The classification is mutual.
Code
Why does the force test correctly identify pseudo-critical edges? If forcing edge i into the MST gives the same total weight as the base MST, then there exists an MST that includes edge i (the one produced by the force test). If some MSTs don’t include it (i.e., it’s not critical — removing it doesn’t increase the weight), then it’s pseudo-critical: present in some MSTs but not all.
Analysis
- Time: O(E² α(V)) — E experiments, each running Kruskal’s in O(E α(V)). For E ≤ 200, this is fast enough.
- Space: O(V + E).
Same skin
- Second-Best MST — one specific skip+replace to find the next-best spanning tree.
- Minimum Spanning Tree with Forbidden Edge — Kruskal’s with skip=-1 for forbidden edge.
- Forced-Edge MST — Kruskal’s with force for the required edge.
- Sensitivity Analysis — determining which edges are robust to weight perturbations.