We’re preparing your current view and syncing the latest data.
You are given an undirected weighted connected graph with n vertices numbered from 0 to n - 1 and an edge list edges where edges[i] = [ui, vi, weighti] represents a bidirectional and weighted edge between nodes ui and vi. A Minimum Spanning Tree (MST) is a subset of the edges that connects all vertices together without cycles and with the minimum possible total edge weight. An edge in edges is critical if its removal from the graph causes the MST to have a strictly larger weight or makes it impossible to connect all vertices. An edge is pseudo-critical if it can appear in some MSTs but is not critical. Your task is to find the indices of critical and pseudo-critical edges in the MST of this graph.
An integer n, representing the number of vertices, and a list edges of length m where each edges[i] = [ui, vi, weighti] represent an edge with weight.
Return a list answer = [critical, pseudoCritical] where critical is a list of indices of critical edges and pseudoCritical is a list of indices of pseudo-critical edges. Both lists are sorted in ascending 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]]
Explanation
Edges 0 and 1 are critical because removing either increases the MST weight. Edges 2, 3, 4, and 5 are pseudo-critical as they can appear in some MSTs but are not critical.