A connected network has n nodes 0 .. n-1 and candidate cables cables[i] = [u, v, cost]
(undirected). Among all cheapest ways to connect every node (minimum spanning trees):
- a cable is essential if it appears in every cheapest layout;
- a cable is optional if it appears in some but not all cheapest layouts.
Return [essential, optional], two sorted lists of cable indices.
Examples
Input: n = 4, cables = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,2,3]]
Output: [[0, 1], [2, 3]]
Explanation: every cheapest layout (weight 4) uses 0-1 and 1-2, plus either 2-3 or 0-3.
Cable 0-2 is never used.
Input: n = 2, cables = [[0,1,5]]
Output: [[0], []]
Constraints
2 <= n <= 100,n - 1 <= len(cables) <= 300,0 <= cost <= 1000- The cables connect all nodes. Target
O(E**2 * alpha(n))after one sort.
Goals
- Compute the minimum spanning tree weight with Kruskal
- Classify an edge by re-running Kruskal without it and with it forced
- Distinguish 'in every MST' from 'in some MST'