Standard Bar Graphs · MST Problems O(E log E) · O(V)
A satellite operator leases ground-station links from bids, each bid quoting one link at a price. The accountant sorts every bid cheapest-first and buys it unless both ends already connect through previously bought links — buying only links that merge two separate station groups, never one that closes a private loop. When every station belongs to one group, the bill is the minimum leasing cost.
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
Sorted bids buy 1 then 3, connecting everything for 4; the 5 bid is skipped.
Input: {"n":4,"edges":[[0,1,1],[1,2,2],[2,3,3],[3,0,4],[0,2,5]]}
Output: 6
The 1, 2, 3 chain wins again; the 4-bid would close a loop and is refused.