Who Connects Each Village to the Cable Network
Implement treeParents
A cable company connects n villages, starting from village 0. All possible cables have different costs, so the cheapest way to connect every village is a single, unique network (a tree). For each village, report which village it is attached to on the way back to village 0 in that network (its parent), using -1 for village 0 itself.
Prim's algorithm builds exactly this tree: it repeatedly attaches the unconnected village that is cheapest to reach, and the village it was attached from is its parent.
Example 1:
Input: weights = [[0,7,3,0,0,0],[7,0,1,5,0,0],[3,1,0,8,4,0],[0,5,8,0,2,9],[0,0,4,2,0,6],[0,0,0,9,6,0]]
Output: [-1,2,0,4,2,4]
Example 2:
Input: weights = [[0,5],[5,0]]
Output: [-1,0]
Example 3:
Input: weights = [[0]]
Output: [-1]
+ 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 … 30) is its cost - ●
All cable costs in the matrix are DISTINCT, so the cheapest network (minimum spanning tree) is unique - ●
The network is grown from village 0. The parent of a village is the village it is connected to on the way to village 0 in the cheapest network - ●
Return an array parent where parent[0] = -1 and parent[i] is the parent of village i (a village that cannot be connected to 0 also gets -1)
weights =