List the Cables of the Cheapest Network
Implement cableList
You are given the possible cables between villages as a symmetric cost matrix, with all costs different. List the cables of the cheapest network that connects the villages (a minimum spanning tree, or a spanning forest when the villages cannot all be connected), each as [u, v, cost] with u < v, ordered by cost.
Kruskal's algorithm sorts the cables and keeps each one unless its two ends are already connected; union-find makes that check fast.
Example 1:
Input: weights = [[0,11,6,5,0,0],[11,0,0,14,12,0],[6,0,0,4,0,7],[5,14,4,0,8,0],[0,12,0,8,0,9],[0,0,7,0,9,0]]
Output: [[2,3,4],[0,3,5],[2,5,7],[3,4,8],[0,1,11]]
Example 2:
Input: weights = [[0,7],[7,0]]
Output: [[0,1,7]]
Example 3:
Input: weights = [[0]]
Output: []
+ 14 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 7 villages numbered 0 … n-1; weights is a symmetric n × n matrix: weights[u][v] = 0 means no cable is possible between u and v, otherwise weights[u][v] (1 … 40) is its cost - ●
All cable costs in the matrix are DISTINCT, so the cheapest set of cables is unique - ●
If the villages cannot all be connected, choose the cheapest cables inside each connected part (a cheapest spanning forest) - ●
Return the chosen cables as rows [u, v, cost] with u < v, ordered by increasing cost (an empty list if there are no cables)
weights =