Skip to content

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.

Hard#1489
LeetCode Problem

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

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

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

Input
n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output
[[],[0,1,2,3]]
Explanation

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

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.

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

  1. Attach each edge's original index, then sort by weight; all later reporting uses input indices, never sorted positions.
  2. Run Kruskal with a disjoint-set union to get the baseline MST weight W.
  3. For each edge, rerun Kruskal skipping it; if fewer than n - 1 edges are accepted or the total exceeds W, the edge is critical.
  4. 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.
  5. 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]]

  1. 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.
  2. 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.
  3. 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.
  4. Excluding edge 6 leaves weight 7, but forcing it gives 6 + 1 + 1 + 2 = 10 > 7, so it is in no MST.
  5. 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.