Problem Statement
Number of Operations to Make Network Connected
You have n computers and some cables. Each cable connects two computers. You are allowed to unplug a cable from where it is and plug it in somewhere else. The question: what is the fewest moves to get every computer joined into one big network, where any computer can reach any other? If it cannot be done, return -1. Here is the key idea. To link n computers into one network you need at least n-1 cables. Think of it like connecting n dots with string: with fewer than n-1 strings you can never reach them all. So if you do not even have n-1 cables, the answer is -1. If you do have enough cables, the only thing that matters is how many separate groups your computers currently form. Each group is an island of connected computers. To join two islands you only need to move one spare cable. So the answer is (number of islands minus 1).
Signals to notice
Brute force first
Try all edge reassignments — exponential.
The key insight
Union-Find: count components and redundant edges. Need components-1 spare edges. If not enough, impossible. O(E × α(V)).
Trace it on n=4, connections=[[0,1],[0,2],[1,2]]
edges=3 >= n-1=3, so not -1. Init parent=[0,1,2,3], components=4
[0,1]: find(0)=0, find(1)=1 differ -> parent[0]=1, components=3
[0,2]: find(0)=1, find(2)=2 differ -> parent[1]=2, components=2
[1,2]: find(1)=2, find(2)=2 same -> redundant edge, skip
All edges processed: components=2 (one connected tree {0,1,2}, plus isolated {3})
return components-1 = 2-1 = 1What must stay true
Redundant edges (connecting already-connected nodes) can be reassigned. Need ≥ components-1 spare edges.
Shape of the loop
if edges < n-1: return -1
parent = [0..n-1]; components = n
for (a, b) in connections:
ra, rb = find(a), find(b)
if ra != rb: union(ra, rb); components -= 1
return components - 1Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not counting redundant edges — answer depends on having enough spare edges to reassign.