Number of Operations to Make Network Connected: Count the Islands
Solve Number of Operations to Make Network Connected by counting connected components with BFS — feasibility check, JavaScript code, and a full walkthrough.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You have a room of computers and a pile of ethernet cables already plugged in. Some machines can talk to each other, some can't. You're allowed to unplug any existing cable and re-plug it anywhere. The question: what's the fewest re-pluggings that make every computer reachable from every other one?
The trap is thinking about which specific cable to move. You never need to. Two numbers decide everything: how many cables you have, and how many separate clusters the network breaks into. Get those, and the answer falls out of a one-line formula.
This is the exact algorithm the visualizer walks through — a feasibility check, then a BFS sweep that counts connected components.
The problem
There are n computers numbered 0 to n - 1, connected by connections, where connections[i] = [a, b] is a cable between computers a and b. You may unplug a cable between two directly connected computers and place it between any two computers that aren't yet linked. Return the minimum number of such moves to make all n computers connected — or -1 if it's impossible.
Input: n = 4, connections = [[0,1], [0,2], [1,2]]
Output: 1
// {0,1,2} form one cluster (with a spare cable between them); 3 is alone.
// Move the redundant cable to link 3 in → everything connected in 1 move.Two facts quietly drive the whole solution:
- A network of
ncomputers needs at leastn - 1cables to be fully connected (that's a spanning tree). Ifconnections.length < n - 1, no amount of rearranging helps — return-1. - Redundant cables are your budget. Any cable inside an already-connected cluster is a spare you can relocate. As long as you clear the
n - 1bar, you always have enough spares.
The brute force baseline
You might try to simulate: find a redundant edge, remove it, drop it between two disconnected computers, repeat until connected. Each "is the graph connected now?" check is its own traversal, and picking which edge to move invites backtracking.
// The tempting-but-wasteful mental model
function makeConnected(n, connections) {
while (!isFullyConnected(n, connections)) {
const spare = findRedundantCable(connections); // a traversal
if (!spare) return -1;
relocate(spare, connections); // another traversal
}
return moveCount;
}Every iteration re-traverses the graph, and you might relocate O(n) cables, so this drifts toward O(n · (V + E)) with a lot of bookkeeping. Worse, it hides the insight. You don't need to know which cable moves or where — only how many moves. Counting beats simulating.
The key insight: components minus one
Picture the network as a set of islands. Each connected component is one island. If there are k islands, connecting them into a single landmass takes exactly k - 1 bridges — one bridge collapses two islands into one, so k islands need k - 1 merges.
Every bridge is a spare cable you relocate. So the answer is simply:
answer = (number of connected components) - 1...provided you have enough cables to build a spanning tree at all. That gives a clean two-step algorithm:
- If
connections.length < n - 1, return-1(impossible). - Otherwise, count connected components and return
components - 1.
You never track redundant cables explicitly. The feasibility check guarantees the spares exist; the component count tells you how many bridges those spares must build.
The optimal solution
This is the JavaScript the visualizer runs. It builds an undirected adjacency list, then scans every node — each unvisited node seeds a fresh component and kicks off a BFS that floods the rest of that component.
var makeConnected = function(n, connections) {
if (connections.length < n - 1) return -1;
let graph = Array.from({ length: n }, () => []);
for (let [from, to] of connections) {
graph[from].push(to);
graph[to].push(from);
}
let visited = new Array(n).fill(false);
let noOfComponents = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
noOfComponents++;
bfs(i, visited, graph);
}
}
return noOfComponents - 1;
};
function bfs(src, visited, graph) {
let q = [src];
visited[src] = true;
while (q.length) {
let curr = q.shift();
for (let neighbor of graph[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}The feasibility guard runs first and short-circuits impossible inputs before any graph is even built. Then the outer loop's job is to find new components — it only calls bfs when it hits a node no previous BFS has reached. Inside bfs, a node is marked visited the instant it's enqueued (not when it's dequeued), which is what stops the same node from being pushed twice.
Walkthrough
Trace n = 4, connections = [[0,1], [0,2], [1,2]]. Adjacency: 0→[1,2], 1→[0,2], 2→[0,1], 3→[]. Feasibility: connections.length = 3, n - 1 = 3, so 3 < 3 is false — we proceed.
| Step | Outer i | Action | visited | Queue | noOfComponents |
|---|---|---|---|---|---|
| 1 | 0 | unvisited → new component, BFS(0), mark 0 | [T,F,F,F] | [0] | 1 |
| 2 | 0 | dequeue 0; enqueue neighbors 1, 2 | [T,T,T,F] | [1,2] | 1 |
| 3 | 0 | dequeue 1; neighbors 0,2 already visited | [T,T,T,F] | [2] | 1 |
| 4 | 0 | dequeue 2; neighbors 0,1 already visited | [T,T,T,F] | [] | 1 |
| 5 | 1 | visited[1] is true → skip | [T,T,T,F] | [] | 1 |
| 6 | 2 | visited[2] is true → skip | [T,T,T,F] | [] | 1 |
| 7 | 3 | unvisited → new component, BFS(3), mark 3 | [T,T,T,T] | [3] | 2 |
| 8 | 3 | dequeue 3; no neighbors | [T,T,T,T] | [] | 2 |
Two components found: {0,1,2} and {3}. Return 2 - 1 = 1. The one relocation takes the spare cable inside {0,1,2} (three nodes only need two edges, but they have three) and re-plugs it to node 3.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Repeated relocate-and-recheck | ~O(n · (V + E)) | O(V + E) | re-traverses the whole graph on every move |
| BFS component count | O(V + E) | O(V + E) | each node dequeued once, each edge inspected twice |
Here V = n and E = connections.length. Building the adjacency list is O(E). The outer loop visits every node once; across all BFS calls, each node is enqueued at most once and each edge is examined from both endpoints, so the traversal is O(V + E) total. Space is the adjacency list plus the visited array plus the queue — all bounded by O(V + E).
Common mistakes
- Skipping the feasibility check. Without the
connections.length < n - 1guard you'll happily returncomponents - 1for an input that can never be connected. The check must come first. - Marking visited on dequeue instead of on enqueue. If you set
visited[neighbor] = trueonly when you pop a node, the same node gets pushed multiple times from different neighbors, inflating the queue and risking a re-count. Mark it the moment it enters the queue. - Counting edges instead of components. The answer is driven by how many islands exist, not how many cables are redundant. Redundancy is guaranteed once you clear the
n - 1bar; you only ever count components. - Off-by-one on the formula. It's
components - 1, notcomponents. One fully-connected graph is already one component and needs zero moves. - Building a directed graph. Cables are bidirectional. Push both
graph[from].push(to)andgraph[to].push(from), or half your components will look isolated.
Where this pattern shows up next
Counting or merging connected components is a whole family of graph problems — some solved with BFS/DFS flooding, others with a Disjoint Set Union (union-find) structure that does the same component bookkeeping incrementally.
- Redundant Connection — the union-find flip side: find the edge that creates a cycle instead of counting islands.
- Course Schedule II — directed-graph traversal producing a topological order.
- Shortest Path in Binary Matrix — BFS again, but for shortest distance on a grid.
- Network Delay Time — weighted shortest paths across a network with Dijkstra.
You can also step through the algorithm interactively and watch the queue fill and components tick up one BFS at a time.
FAQ
Why is the answer the number of components minus one?
Each connected component is an isolated island. To fuse k islands into a single connected network you need k - 1 links, because every link you add merges two islands into one and reduces the island count by exactly one. Starting at k islands and ending at 1 means k - 1 merges. Every merge reuses a spare (redundant) cable, so no new hardware is needed as long as spares exist.
When does the problem return -1?
When there simply aren't enough cables. Connecting n computers requires a minimum of n - 1 cables (a spanning tree). If connections.length < n - 1, no rearrangement can ever bridge every machine, so the answer is -1. The solution checks this first, before building the graph or counting anything.
Could I solve this with union-find instead of BFS?
Yes. A Disjoint Set Union structure would union the two endpoints of every cable, then count how many distinct roots remain — that root count is the number of connected components. Return roots - 1 after the same connections.length < n - 1 guard. BFS and union-find give identical answers here; the visualizer uses BFS because the queue and visited array make the component-flooding visible step by step.
Why mark a node visited when enqueuing rather than when dequeuing?
Because a node can be a neighbor of several already-queued nodes. If you wait until you dequeue it to mark it, each of those neighbors will push a fresh copy into the queue before any of them is processed, so the node gets enqueued multiple times and may even be counted or traversed redundantly. Marking it visited the instant it enters the queue guarantees each node is added exactly once.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.