Number of Operations to Make Network Connected
Medium · Graphs · Depth-First Search · Breadth-First Search · Union Find · Graph
Problem
There are n computers numbered 0 to n - 1, joined by cables: connections[i] = [a, b] is a cable between computers a and b. Two computers can talk if a chain of cables joins them.
In one operation you may unplug any cable and plug it in between two computers that are not directly connected. Return the fewest operations needed so that every computer can talk to every other, or -1 if that is impossible.
Examples
Input: n = 5, connections = [[0,1],[0,2],[1,2],[3,4]] Output: 1
The cable 1-2 is spare; moving it to join the piece {3, 4} to the rest connects everything.
Input: n = 4, connections = [[0,1],[2,3]] Output: -1
Four computers need at least three cables, and only two exist.
Input: n = 3, connections = [[0,1],[1,2]] Output: 0
Every computer can already reach every other.
Constraints
- 1 <= n <= 10^5
- 1 <= len(connections) <= min(n · (n - 1) / 2, 10^5)
- connections[i] == [a, b] with 0 <= a, b < n and a != b
- No cable is listed twice
Approaches
- Spread labels until nothing changes — time O(n · E), space O(n)
Follow-up
Only the count of pieces matters here, so any way of counting connected components works: union-find, DFS or BFS. Union-find also counts the spare cables on the way (each cable whose ends were already together), and it handles cables arriving one at a time, which a DFS would have to redo from scratch.
Related problems
Start free on Cariara · Coding problems · System design studio
