Medium · Spare-Edge DSU
Understand → Visualise → Practice.
Cables may be moved between computers. Return the minimum moves to connect all n computers, or −1 if too few cables exist.
Connecting c components needs c − 1 cables. Any network with at least n − 1 cables has enough spares inside its components, so the answer is c − 1, or −1 with too few cables.
With fewer than n − 1 cables, connecting n computers is impossible.
Build the components with union-find.
Return the number of components minus one.
O((n + e) α(n)) time and O(n) space.
Counting redundant cables is unnecessary once the total is at least n − 1.
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.