Classify each edge of a weighted undirected graph as critical, pseudo-critical, or neither with respect to its minimum spanning tree(s).
Problem
You are given a connected, undirected, weighted graph with n vertices labeled from 0 to n - 1. Each edge is described by three integers [u, v, w], meaning there is an edge between vertices u and v with weight w.
A minimum spanning tree (MST) is a subset of edges that connects all vertices with minimum possible total weight.
An edge is:
- critical if removing it makes it impossible to form an MST with the same minimum total weight.
- pseudo-critical if it can appear in some MST, but is not critical.
Return the indices of all critical edges and all pseudo-critical edges.
Notes
- Edge indices refer to the position of each edge in the input list.
- The graph is guaranteed to be connected.
- If an edge is neither critical nor pseudo-critical, do not include it in either list.
Input Format
n: number of vertices.edges: list of edges where each edge is[u, v, w].
Each edge has an implicit original index based on its position in the input.
Output Format
Return two lists:
- the indices of all critical edges
- the indices of all pseudo-critical edges
Constraints
1 <= n <= 100n - 1 <= edges.length <= min(200, n * (n - 1) / 2)0 <= u, v < nu != v1 <= w <= 1000- The graph is connected.
These constraints are consistent with a solution that repeatedly computes MSTs using a greedy + DSU approach.
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
One minimum spanning tree has total weight 7. Edges 0 and 1 are critical because removing either one forces a higher-cost solution. Edges 2, 3, 4, and 5 are pseudo-critical because each can be part of some MST, but none is necessary in every MST.
Example 2
Input
n = 4 edges = [[0,1,1],[1,2,2],[2,3,3],[0,3,4],[0,2,5]]
Output
[[0,1,2],[]]
Explanation
The unique MST uses edges 0, 1, and 2. Removing any of them increases the MST cost, so they are all critical. No other edge can be part of an MST with the same minimum cost.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.