Number of Operations to Make Network Connected

There are n computers (0 .. n-1) and connections[i] = [a, b] is a cable directly connecting a and b. You may remove any cable and reattach it between any two computers. Return the minimum number of such moves to make all computers connected, or -1 if it's impossible.

Hints

· Stuck? Reveal one nudge at a time.

You can't create new cables — connecting n computers needs at least n-1.

If there are fewer than n-1 cables, it's impossible: return -1.

Otherwise the answer is the number of connected components minus one.

Common doubts

Each connected component beyond the first needs exactly one link to join the rest, so joining c components takes c-1 moves.

With ≥ n-1 cables and c components, at least c-1 edges are redundant (form cycles), and those are exactly the cables you can reattach.

Both count components; union-find also naturally counts redundant edges if you want to reason about spares.

Interview follow-ups

· What an interviewer asks next.

Track redundant edges (union of already-connected endpoints) and pair them with the components needing a link.

Connectivity becomes strong vs weak; the counting differs (you'd consider strongly connected components).

Fun facts

LeetCode 1319 — a component-count problem dressed up as network rewiring.
The n-1 lower bound is just 'a tree on n nodes has n-1 edges'.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Move the redundant cable in {0,1,2} to connect computer 3.

Example 2

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2
Two extra components (4 and 5) each need one link.

Constraints

- 1 <= n <= 10^5 - 0 <= connections.length <= 10^5 - no duplicate cables, no self-loops

Two facts decide this instantly:

Connecting n computers needs at least n-1 cables. If you have fewer than n-1 cables total, it's impossible — return -1.
Otherwise, the answer is components - 1: the network currently forms some number of connected components, and you need one link to join each extra component to the rest. There are always enough spare cables (redundant edges, whose endpoints were already connected) to do it — that's guaranteed the moment you have ≥ n-1 cables.

So the whole problem is counting connected components — via union-find (count merges) or a DFS/BFS flood. O(n + E).

Prerequisites

Before you start

· Concepts used directly in the solution.

Component count. how many disjoint groups exist.

Cable arithmetic. need components-1 links; need ≥ n-1 cables.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“When is it impossible?”

When there are fewer than n-1 cables.

“Where do the new links come from?”

Redundant (cycle) cables, which always suffice if you have ≥ n-1.

The ideal opening — say it like this

If there are fewer than n-1 cables it's impossible; otherwise I just need components-1 moves.

So I count connected components with union-find or a flood fill.

Understand the problem

Worked example — n = 4, connections [[0,1],[0,2],[1,2]]

3 cables ≥ n-1 = 3; components = {0,1,2}, {3} -> 2
answer = 2 - 1 = 1

Key observations

1Aha

Need at least n-1 cables

Fewer ⇒ impossible (-1).

2Aha

Answer is components - 1

One link per extra component.

3Aha

Spare cables always suffice

Redundant edges cover the needed links once you have ≥ n-1.

Brute force vs optimal

	DFS component count	Union-Find
Count via	flood each unvisited computer	merges (n minus successful unions)
Time	O(n+E)	O(n + E·α)
Answer	components - 1	components - 1

Both count the same components. Full code is in the Approaches selector below.

Summary

Key takeaway

If cables < n-1, return -1. Otherwise the answer is (number of connected components) - 1. Count components with union-find or DFS. O(n + E).

if edges < n-1: return -1
return componentCount - 1