Number of Operations to Make Network Connected
There are n computers numbered 0 to n - 1, and a list of connections where connectionsi = [ai, bi] represents a direct cable between computer ai and computer bi. Any cable can be unplugged and used to connect two computers that don't currently have a direct or indirect connection between them. Return the minimum number of times you need to move a cable so that every computer is connected, or -1 if there aren't enough cables to do it. Union every existing cable with union-find exactly like Kruskal's cycle check — a cable whose endpoints are already connected is a spare cable you can move elsewhere. The answer is simply the number of separate groups left, minus one.
Constraints
- 1 ≤ n ≤ 105
- 1 ≤ connections.length ≤ min(n * (n - 1) / 2, 105)
- connectionsi.length == 2
- 0 ≤ ai, bi < n
- ai != bi
- There are no repeated connections
Example
n = 4, connections = [[0,1],[0,2],[1,2]]1Explanation Cable 1–2 is spare (0 and 1, and 0 and 2, already connect them indirectly). Move it to reach computer 3: 1 operation.
In plain terms
- Spare cable
- A connection between two computers that are already reachable from each other — moving it elsewhere costs nothing extra.
Union every cable; spare cables become moves, leftover groups become the answer
Cable 0–1: computers 0 and 1 are in separate groups — union them. Groups: 3.
What happens in this step
cable 0–1
find(0)=0, find(1)=1 → different roots
union(0, 1) — needed, used=1
Groups: {0,1}, {2}, {3} → 3 groups leftSteps to visualize
- If there are fewer than n - 1 cables, it is impossible — return -1.
- Union the endpoints of every cable, exactly like the cycle check in Kruskal.
- A cable whose endpoints are already connected is spare — it never grows the tree.
- Count the groups left once every cable is processed; the answer is groups - 1.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Cable 0–1: computers 0 and 1 are in separate groups — union them. Groups: 3.
What happens in this step
cable 0–1
find(0)=0, find(1)=1 → different roots
union(0, 1) — needed, used=1
Groups: {0,1}, {2}, {3} → 3 groups leftSolution
function makeConnected(n, connections) {
if (connections.length < n - 1) return -1;
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
function union(a, b) {
const rootA = find(a);
const rootB = find(b);
if (rootA === rootB) return false;
parent[rootA] = rootB;
return true;
}
let components = n;
for (const [a, b] of connections) {
if (union(a, b)) {
components--;
}
}
return components - 1;
}- Time
- O(n + m · α(n))
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
n = 4, connections = [[0,1],[0,2],[1,2]] | 1 | example from the docstring |
n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] | 2 | three separate groups need two spare cables to join |
n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] | -1 | fewer than n - 1 cables makes it impossible |
n = 5, connections = [[0,1],[1,2],[2,3],[3,4]] | 0 | already one connected group — no moves needed |
n = 1, connections = [] | 0 | smallest valid input, a single computer with no cables |
n = 2, connections = [] | -1 | two computers with zero cables cannot be connected |
n = 4, connections = [[0,1],[1,2],[2,3],[0,3],[0,2]] | 0 | more cables than needed, several of them spare, already one group |