1489. Find Critical and Pseudo Critical Edges in Minimum Spanning Tree

Practice Find Critical and Pseudo Critical Edges in Minimum Spanning Tree for free on NudgeCode: Hard, Graph pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

You are given a connected, undirected, weighted graph with n nodes labeled 0 to n - 1. edges[i] = [a, b, weight] is edge number i. A minimum spanning tree (MST) is a subset of edges that connects all nodes, has no cycle, and has the smallest possible total weight.

• An edge is critical if every MST contains it (removing it from the graph makes the MST weight larger).
• An edge is pseudo-critical if some MSTs contain it and some do not.

Return [critical, pseudoCritical]: two lists of edge indices, each sorted in ascending order.

Example

n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
->  [[0,1],[2,3,4,5]]

Constraints

• 2 <= n <= 100
• 1 <= edges.length <= 200
• 1 <= weight <= 1000
• The graph is connected; no pair of nodes has two edges