Standard Bar Graphs · MST Problems O(E log E) · O(V + E)
A substation cluster must be wired into one grid at minimum trenching cost: pick a subset of cable links so every substation is powered and no link is wasted. Starting from any substation, the planner always extends the grid through the cheapest cable that reaches new ground — a priority queue serves up that cable — until the whole cluster is lit.
Input: An integer n (vertices 0..n-1) and an edge list edges where [u, v, w] is an undirected link of cost w.
Output: Return the total weight of the minimum spanning tree.
1 <= n <= 10^31 <= edges.length <= n * (n - 1) / 21 <= w <= 10^6The graph is connected and undirectedInput: {"n":3,"edges":[[0,1,5],[1,2,3],[0,2,1]]}
Output: 4
The 1-cost and 3-cost links connect all three stations for a total of 4.
Input: {"n":4,"edges":[[0,1,1],[1,2,2],[2,3,3],[3,0,4],[0,2,5]]}
Output: 6
Links 1, 2 and 3 chain every station together; nothing heavier is needed.