Given a connected, weighted, undirected graph, classify each edge as critical, pseudo-critical, or neither with respect to the graph's minimum spanning tree. An edge is critical if removing it increases the MST cost or disconnects the graph. An edge is pseudo-critical if it can appear in some MST. Pattern focus: Kruskal. Use repeated MST computations with forced/excluded edges.
n = number of nodes, edges = list of [u, v, w] with implicit edge indices by input order
two arrays: critical edge indices and pseudo-critical edge indices
Example 1:
Input:
n = 4 edges = [[1,2,1],[2,3,1],[3,4,1],[1,4,1],[1,3,2],[2,4,2]]
Output:
[[],[0,1,2,3]]
Explanation:
Any three of the four unit-weight cycle edges can form an MST, so they are pseudo-critical and none is critical.
Example 2:
Input:
n = 4 edges = [[1,2,1],[2,3,2],[3,4,3],[1,4,10],[1,3,4],[2,4,5]]
Output:
[[0,1,2],[]]
Explanation:
The unique MST uses edges 0, 1, and 2, so all are critical.
Example 3:
Input:
n = 4 edges = [[1,2,1],[2,3,1],[3,4,2],[1,4,2],[1,3,2]]
Output:
[[0,1],[2,3]]
Explanation:
Edges 0 and 1 are required in every MST, while edges 2 and 3 can appear in some MSTs.