Number of operations to make network connected

Hard

Components minus one, if you have spare cables

Problem

Given n computers and cables, return the minimum cables to move to connect all (or -1).

In simple words

Count connected groups with union-find; joining k groups needs k-1 spare cables (if enough exist).

The idea

Connecting c components needs c-1 cables, and a cable is spare whenever its endpoints were already connected. Count components and redundant edges with union-find; the answer is c-1 provided the spares suffice.

The trick

Impossible when edges < n-1 — there simply are not enough cables.
Redundant edges are exactly the unions that fail.
Answer = componentCount - 1.

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n = 4, connections = [[0,1],[0,2],[1,2]]
Output:: 1
Explanation:: One spare cable links the lonely computer → 1.

Example 2

Input:: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output:: 2
Explanation:: Two extra cables join 3 groups → 2.

Example 3

Input:: n = 3, connections = [[0,1]]
Output:: -1
Explanation:: Too few cables → -1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.