Standard Bar Graphs · MST Problems O(E + V α(V)) · O(V)
A server hall's racks are linked by cables, some of them redundant. Technicians may unplug a cable between two already-linked racks and re-run it between any disconnected pair. The facilities lead needs the fewest such re-cabling moves to make the whole hall one network — or proof that there simply aren't enough cables to go round.
Input: An integer n (racks 0..n-1) and a list connections where [a, b] is a link between racks a and b.
Output: Return the minimum number of cable moves needed to connect all racks, or -1 if impossible.
1 <= n <= 10^51 <= connections.length <= 10^5No duplicate or self linksInput: {"n":4,"connections":[[0,1],[0,2],[1,2]]}
Output: 1
Racks 0-1-2 form one cluster and rack 3 is isolated; the loop's spare cable reaches it.
Input: {"n":6,"connections":[[0,1],[0,2],[0,3],[0,4],[0,5]]}
Output: 0
The hub already links every rack.