DSA problem
Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Given a weighted undirected connected graph with n vertices and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi, find the set of critical and pseudo-critical edges for the graph's Minimum Spanning Tree (MST).
An MST edge whose removal would increase the MST weight (or disconnect the graph) is critical. An MST edge that appears in some MST but not in every MST is pseudo-critical — its removal still allows an MST of the same total weight, but it can also be the chosen edge in an alternate MST of the same weight. Return the indices of these edges in two lists.
The straightforward approach exploits a classical fact: an edge e is critical iff removing it from the graph either disconnects the graph or yields an MST with strictly greater weight than the base MST. An edge is pseudo-critical iff forcing it into the MST first still produces an MST of base weight, AND it is not critical.
So for each edge index i: compute the base MST weight W once with Kruskal's. Then for each i, recompute the MST while skipping edge i — if the result exceeds W (or the graph is disconnected), i is critical. Otherwise recompute while forcing edge i to be the first chosen edge — if the result equals W, i is pseudo-critical. With at most m edges, the total work is O(m * E α(n)), comfortably fast under the constraints.
Examples
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]]n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]][[],[0,1,2,3]]n = 2, edges = [[0,1,5]][[0],[]]Constraints
- 2 <= n <= 100
- 1 <= edges.length <= min(200, n * (n - 1) / 2)
- edges[i].length == 3
- 0 <= ai < bi < n
- 1 <= weighti <= 1000
- All pairs (ai, bi) are distinct.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.