Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Hard · Advanced Graphs · Union Find · Graph · Sorting · Minimum Spanning Tree
Problem
You are given a connected, undirected, weighted graph with n vertices numbered 0 to n - 1, and a list edges where edges[i] = [a_i, b_i, weight_i]. A minimum spanning tree (MST) is a set of n - 1 edges that connects every vertex with the smallest possible total weight. A graph can have several MSTs.
Classify the edges by their index i:
- an edge is critical if it belongs to every MST: without it, the best spanning tree is heavier (or there is none);
- an edge is pseudo-critical if it belongs to some MSTs but not all of them.
Return [critical, pseudoCritical], two lists of edge indices. Each list may be in any order. Edges in no MST appear in neither list.
Examples
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]]
Edges 0 and 1 are the only weight-1 edges and are in every MST. Edges 2 and 3 are interchangeable, as are 4 and 5, so those four are pseudo-critical. Edge 6 is never used.
Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]] Output: [[],[0,1,2,3]]
The four edges form a cycle of equal weights: any three of them make an MST, so all four are pseudo-critical.
Input: n = 3, edges = [[0,1,1],[1,2,2]] Output: [[0,1],[]]
The graph is a tree, so its two edges are in the only spanning tree: both critical.
Constraints
- 2 <= n <= 100
- 1 <= len(edges) <= min(200, n · (n - 1) / 2)
- 0 <= a_i < b_i < n
- 1 <= weight_i <= 1000
- no two edges join the same pair of vertices
- the graph is connected
Approaches
- Baseline: list every spanning tree — time O(C(E, n - 1) · n), space O(C(E, n - 1))
Follow-up
Two extra Kruskal runs per edge give O(E² · α(n)). Grouping the edges by weight and finding bridges in each group's contracted graph classifies every edge in O(E log E). The use cases list the edges that are in no MST, and ask for the cheapest spanning tree that must include a given edge.
Related problems
Start free on Cariara · Coding problems · System design studio
