Practice Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Problem Statement
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 that which can appear in some MSTs but not all. Note that you can return the indices of the edges in any order.
Source: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 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]]
[[0,1],[2,3,4,5]]
Using the original zero-based edge indices, every MST contains edges 0 and 1, then chooses one of edges 2 and 3 and one of edges 4 and 5. Each of these four trees costs 1 + 1 + 2 + 3 = 7. Removing edge 0 or edge 1 raises the best achievable weight to 8, so both are critical. Edges 2 through 5 appear in some, but not all, of the weight-7 trees and are pseudo-critical. Edge 6 belongs to neither group: forcing it into a spanning tree costs at least 10.
# Example 2
n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
[[],[0,1,2,3]]
The four weight-1 edges form a cycle through all four vertices. A spanning tree needs three edges, and removing any one edge from this cycle leaves a connected path of total weight 3. Consequently there are four MSTs. Every edge is absent from one MST and present in the other three: none is critical, and all four are pseudo-critical. Being selected by one particular run of an MST algorithm does not make an edge critical; the classification must account for all optimal trees.
Constraints
How to solve Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Compute the MST weight once, then classify each edge with two more MST runs: excluding it (if the weight rises or the graph disconnects, it is critical) and forcing it in first (if the weight stays equal, it is pseudo-critical).
Why brute force is not enough
Enumerating every spanning tree to see which edges appear in all or some minimum ones is exponential in the edge count. With n at most 100 and edges.length at most 200, running Kruskal about 2E + 1 times is deliberately affordable.
Approach
- Attach each edge's original index, then sort by weight; all later reporting uses input indices, never sorted positions.
- Run Kruskal with a disjoint-set union to get the baseline MST weight W.
- For each edge, rerun Kruskal skipping it; if fewer than n - 1 edges are accepted or the total exceeds W, the edge is critical.
- Otherwise rerun Kruskal with the edge united first and its weight pre-added; a total equal to W makes it pseudo-critical, and anything larger means it is in no MST.
- Return the two index lists; a critical edge is not repeated in the pseudo-critical list.
Walkthrough of Example 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]] → [[0,1],[2,3,4,5]]
- By weight the indices order as 0, 1 (weight 1), 2, 3 (weight 2), 4, 5 (weight 3), 6 (weight 6). Kruskal accepts 0, 1, 2, skips 3 since 0 and 3 are already joined, accepts 4, skips 5 and 6: W = 7.
- Excluding edge 0 forces edges 1, 2, 3, 4 for 1 + 2 + 2 + 3 = 8 > 7, so edge 0 is critical; excluding edge 1 also gives 8, so edge 1 is critical.
- Excluding edge 2 leaves 0, 1, 3, 4 at weight 7, so it is not critical; forcing it first gives 2 + 1 + 1 + 3 = 7, so it is pseudo-critical. Edges 3, 4 and 5 behave identically.
- Excluding edge 6 leaves weight 7, but forcing it gives 6 + 1 + 1 + 2 = 10 > 7, so it is in no MST.
- Output [[0,1],[2,3,4,5]].
Time and space
Time O(E^2 * alpha(n)) · Space O(n + E). E is the edge count and n the vertex count; after one O(E log E) sort, about 2E Kruskal passes each touch E edges with near-constant union-find work, reusing the sorted list.
Interview pitfalls
- Losing the original indices after sorting and returning sorted positions.
- Skipping the connectivity check when an edge is excluded; removing a bridge yields a forest, and comparing weights alone misses it.
- Forgetting to unite the forced edge's endpoints or to add its weight before the Kruskal pass.
- Assuming the edge chosen by one Kruskal run is critical; with equal weights, as in example 2, every edge may be replaceable.
Follow-up questions interviewers ask
- With 10^5 edges, how would you group edges by equal weight and use bridge-finding on a contracted graph to classify them in near-linear time?
- How would you count the number of distinct minimum spanning trees rather than classify edges?
Further reading on the technique: Kruskal's algorithm
Related LeetCode Problems
Practice more problems similar to Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.