Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
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 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 MST:
- A critical edge is an
MSTedge whose deletion from the graph would cause theMSTweight to increase. - A pseudo-critical edge is an edge that can appear in some
MSTsbut not all.
Return a list containing two lists:
- The indices of all critical edges.
- The indices of all pseudo-critical edges.
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]]Edges 0 and 1 appear in all MSTs, while edges 2, 3, 4, and 5 appear only in some MSTs.
Example 2
Input
n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]Output
[[],[0,1,2,3]]Since all 4 edges have equal weight, choosing any 3 edges yields an MST, so all edges are pseudo-critical.
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.
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.