Watch 10 video solutions for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree, a hard level problem involving Union Find, Graph, Sorting. This walkthrough by NeetCodeIO has 15,790 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: 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]] Explanation: The figure above describes the graph. The following figure shows all the possible MSTs:Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output. The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.
Example 2:
Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]] Output: [[],[0,1,2,3]] Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.
Constraints:
2 <= n <= 1001 <= edges.length <= min(200, n * (n - 1) / 2)edges[i].length == 30 <= ai < bi < n1 <= weighti <= 1000(ai, bi) are distinct.Problem Overview: You are given an undirected weighted graph. Some edges are critical to the Minimum Spanning Tree (MST), meaning removing them increases the total MST weight or makes it impossible to form an MST. Others are pseudo‑critical, meaning they can appear in at least one valid MST but are not strictly required. The task is to classify each edge into these two groups.
Approach 1: Kruskal's Algorithm with Union-Find (Baseline MST) (Time: O(E log E + E α(V)), Space: O(V))
Start by building the baseline MST using Kruskal's algorithm. Sort all edges by weight, then use a Union-Find (Disjoint Set Union) structure to connect components while avoiding cycles. This gives the minimum possible total MST weight. The DSU structure allows near constant-time find and union operations using path compression and union by rank. This baseline weight becomes the reference for determining whether removing or forcing an edge changes the MST.
Approach 2: Kruskal's Algorithm with Edge Exclusion/Inclusion (Time: O(E^2 α(V)), Space: O(V))
For each edge, run Kruskal twice. First, exclude the edge and rebuild the MST. If the total weight increases or an MST cannot be formed, that edge is critical. Next, force the edge to be included before running Kruskal on the remaining edges. If the resulting MST weight equals the baseline weight, the edge is pseudo‑critical. This works because Kruskal always constructs the optimal tree given the constraints. Although this repeats MST construction multiple times, the DSU operations remain efficient.
Approach 3: Kruskal's Algorithm with Subset Construction (Time: O(E^2 α(V)), Space: O(V))
Another variant groups edges by weight and processes subsets of edges with equal weights. Within each group, temporarily test which edges can connect components formed by previous weights. Using DSU snapshots or staged unions, you identify edges that are mandatory versus optional within that weight layer. Edges that always connect distinct components become candidates for critical edges, while edges that could appear in multiple valid connections become pseudo‑critical. This approach avoids some redundant recomputation but still relies heavily on the structure of minimum spanning tree construction.
Recommended for interviews: The standard expectation is the edge exclusion/inclusion technique built on Kruskal's algorithm. It clearly demonstrates understanding of MST properties and how Union-Find maintains connected components. Start by explaining MST construction with sorted edges and DSU, then show how removing or forcing edges reveals whether they are critical. Interviewers prefer this method because it is easy to reason about and directly leverages graph fundamentals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Baseline Kruskal MST with Union-Find | O(E log E) | O(V) | Used to compute the reference MST weight before testing edge criticality |
| Kruskal with Edge Exclusion/Inclusion | O(E^2 α(V)) | O(V) | Most common solution; straightforward method to classify edges by recomputing MST |
| Kruskal with Subset Construction | O(E^2 α(V)) | O(V) | Useful when grouping edges by weight to reduce redundant MST checks |