Number of Operations to Make Network Connected
mediumTime: O(n + E)Space: O(n)
Recognize the pattern
minimum edges to make graph connectedcount componentsspare edges from redundant connections
Brute force idea
Try all edge reassignments — exponential.
Better approach
Union-Find: count components and redundant edges. Need components-1 spare edges. If not enough, impossible. O(E × α(V)).
Key invariant
Redundant edges (connecting already-connected nodes) can be reassigned. Need ≥ components-1 spare edges.
Watch out for
Not counting redundant edges — answer depends on having enough spare edges to reassign.