Number of Operations to Make Network Connected
mediumTime: O(n + E)Space: O(n)
Signals to notice
minimum edges to make graph connectedcount componentsspare edges from redundant connections
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)).
What must stay true
Redundant edges (connecting already-connected nodes) can be reassigned. Need ≥ components-1 spare edges.
Easy way to go wrong
Not counting redundant edges — answer depends on having enough spare edges to reassign.