Number of Operations to Make Network Connected
Find the fewest cable moves that connect every computer in a network: check there are at least n - 1 cables, then count connected components with union-find.
Problem Understanding
Number of Operations to Make Network Connected: n computers are joined by connections. In one operation you may unplug a cable and plug it between any two computers. Return the minimum number of operations to connect all computers, or -1 if it is impossible.
Examples: n 4, [[0,1],[0,2],[1,2]] → 1; n 6, [[0,1],[0,2],[0,3],[1,2],[1,3]] → 2; n 6, [[0,1],[0,2],[0,3],[1,2]] → -1.
The Intuition: Count Groups, Not Cables
Which cables you move does not matter, only how many separate groups exist:
- Too few cables (fewer than n − 1): impossible.
- Otherwise spare cables always exist, and each move joins two groups.
- Count the groups with union-find, exactly as in Redundant Connection, where a cable whose ends share a root is the redundant one. Here those are the spare cables.
The component count is the same quantity Number of Islands computes on a grid.
Interactive Walkthrough
COLOUR = GROUP (PLAIN = ALONE) · GREEN CABLE = MERGED · AMBER = SPARE
n GROUPS
components
6
spare
0
answer
:
5 cables ≥ 5, so enough exist. Every computer starts as its own group: 6 components
Next
Cable 0-1: roots 0 and 1 differ, so merge them: 5 components left
cables
n
Computers are colored by group, so each merge recolors a whole group. Merging cables turn green and spare ones amber. Try Example 3 for the early -1.
Dry Run Table
Input: n = 6, cables 0-1, 0-2, 0-3, 1-2, 1-3.
| Cable | Roots | Effect | Components |
|---|---|---|---|
| 0-1 | 0, 1 | merge | 5 |
| 0-2 | 0, 2 | merge | 4 |
| 0-3 | 0, 3 | merge | 3 |
| 1-2 | 0, 0 | spare | 3 |
| 1-3 | 0, 0 | spare | 3 |
Answer: 3 − 1 = 2 (computers 4 and 5 each need a moved cable).
The Solution Template
Union-find with path halving and a component counter.
Number of Operations to Make Network Connected Code
1var makeConnected = function(n, connections) {2 if (connections.length < n - 1) return -1;3 const parent = Array.from({ length: n }, (_, i) => i);4 const find = (x) => {5 while (parent[x] !== x) {6 parent[x] = parent[parent[x]];7 x = parent[x];8 }9 return x;10 };11 let components = n;12 for (const [a, b] of connections) {13 const ra = find(a), rb = find(b);14 if (ra !== rb) {15 parent[rb] = ra;16 components--;17 }18 }19 return components - 1;20};
Edge Cases & Common Mistakes
- Check the cable count first: without it you return components − 1 even when there are not enough cables.
- Already connected: components = 1, answer 0.
- Isolated computers: they count as components even with no cables.
- Counting spare cables instead: spares only matter for the impossibility check, which n − 1 already covers.
- Deep recursion in find: use the iterative version or path compression.
Summary
If cables < n − 1 return −1; otherwise count connected components with union-find and return components − 1. O(n + E · α(n)) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet