Number of Operations to Make Network…

1. Define the problem

Number of Operations to Make Network Connected

There are n computers numbered 0 to n - 1, and a list of connections where connections_i = [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 ≤ 10⁵
1 ≤ connections.length ≤ min(n * (n - 1) / 2, 10⁵)
connections_i.length == 2
0 ≤ ai, bi < n
ai != bi
There are no repeated connections

Example

Inputn = 4, connections = [[0,1],[0,2],[1,2]]

Output1

Explanation Cable 1–2 is spare (0 and 1, and 0 and 2, already connect them indirectly). Move it to reach computer 3: 1 operation.

2. Know the words first

In plain terms

Spare cable: A connection between two computers that are already reachable from each other — moving it elsewhere costs nothing extra.

3. Visualize the solution

Union every cable; spare cables become moves, leftover groups become the answer

cable0–1

cable0–2

cable1–2

Statusgroups: 4

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 left

Step 1 of 4

Steps 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.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union every cable; spare cables become moves, leftover groups become the answer

cable0–1

cable0–2

cable1–2

Statusgroups: 4

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 left

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

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)

6. Test cases

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

Number of Operations to Make Network Connected