Union-Find Interview Problem: Connecting a Network

There are n computers, numbered 0 to n − 1, and a list of cables connections; each [a, b] joins computers a and b. You may unplug any cable and plug it in between any two computers. Return the smallest number of such moves that leaves every computer connected to every other, directly or through others, or −1 if it cannot be done.

Examples

Input	Output	Why
`n = 4, connections = [[0, 1], [0, 2], [1, 2]]`	`1`	Move the cable between 1 and 2 to join computer 3.
`n = 6, connections = [[0, 1], [0, 2], [0, 3], [1, 2]]`	`-1`	Five cables are needed to connect six computers; there are four.
`n = 5, connections = [[0, 1], [0, 2], [3, 4], [2, 3]]`	`0`	Already connected.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ |connections| ≤ 10⁵
No cable joins a computer to itself

Hints

Hint 1

Connecting n computers needs at least n − 1 cables. With fewer, the answer is −1 whatever you do.

Hint 2

With enough cables, the answer is the number of separate groups minus one: each move can join two groups, and a group with a cycle always has a cable to spare.

Hint 3

Count the groups with union-find: start with every computer in its own set and merge the two ends of each cable. Each successful merge reduces the count by one.

Where people lose marks

Checking only that the graph is connected and forgetting the cable count: with fewer than n − 1 cables, −1 is the answer even if the groups could be joined in principle.
Counting groups as the number of distinct parent values without calling find: parents are not roots until the path is compressed.
Union without find: setting parent[a] = b links the nodes, not their groups, and can create cycles in the forest.
Recursion depth in find on long chains in languages with small stacks; use an iterative find or union by size.

Dry run on `7,[[0,1],[1,2],[2,0],[3,4],[4,5],[5,3]]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 6

Step 1 / 6

parent (computers 0..n−1)
10112233445566
groups6spare0
Cable 0–1: it joins two groups; root 0 is attached under root 1. 6 groups remain.
Step 2 / 6

parent (computers 0..n−1)
10212233445566
groups5spare0
Cable 1–2: it joins two groups; root 1 is attached under root 2. 5 groups remain.
Step 3 / 6

parent (computers 0..n−1)
20212233445566
groups5spare1
Cable 2–0: both ends are already in the same group (root 2), so this cable closes a cycle and is spare.
Step 4 / 6

parent (computers 0..n−1)
20212243445566
groups4spare1
Cable 3–4: it joins two groups; root 3 is attached under root 4. 4 groups remain.
Step 5 / 6

parent (computers 0..n−1)
20212243545566
groups3spare1
Cable 4–5: it joins two groups; root 4 is attached under root 5. 3 groups remain.
Step 6 / 6

parent (computers 0..n−1)
20212253545566
groups3spare2
Cable 5–3: both ends are already in the same group (root 5), so this cable closes a cycle and is spare. 3 groups need 2 moves, and there are 2 spare cables, which is enough.

How to think about it

Two observations reduce the problem to counting.

Enough cables is necessary. Any connected network on n computers contains a spanning tree with n − 1 cables, so with fewer the answer is −1.
Enough cables is sufficient. If there are c separate groups, the cables inside them number at least n − c for the groups to be connected internally; any beyond that close cycles and can be moved without disconnecting anything. With at least n − 1 cables there are at least c − 1 spare ones, and each joins two groups. So the answer is c − 1, and no fewer moves can work, since one move joins at most two groups.

Counting groups is what union-find is for. Each computer points to a parent; the root of its tree names its group. find follows parents to the root, and compresses the path on the way so later finds are fast. union attaches the root of the smaller tree under the root of the larger. With both optimisations every operation takes amortised time that is effectively constant (the inverse Ackermann function, below 5 for any input that fits in memory).

Union-find answers "are these two connected?" while edges keep arriving, which depth-first search cannot do without starting again. Redundant connection, accounts merge, number of islands with land added one cell at a time, and Kruskal's minimum spanning tree all use it.

Complexity. Time O((n + E) α(n)) · Space O(n)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def network_cables(n, connections):
    if len(connections) < n - 1:
        return -1                          # a connected network needs n - 1 cables
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x

    groups = n
    for a, b in connections:
        ra, rb = find(a), find(b)
        if ra != rb:
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra                # smaller tree under the larger
            size[ra] += size[rb]
            groups -= 1
    return groups - 1

#include <vector>
#include <numeric>
#include <utility>

int solve(int n, const std::vector<std::vector<int>>& connections) {
    if (static_cast<int>(connections.size()) < n - 1) return -1;
    std::vector<int> parent(n), size(n, 1);
    std::iota(parent.begin(), parent.end(), 0);
    auto find = [&](int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
        return x;
    };
    int groups = n;
    for (const auto& c : connections) {
        int ra = find(c[0]), rb = find(c[1]);
        if (ra == rb) continue;
        if (size[ra] < size[rb]) std::swap(ra, rb);
        parent[rb] = ra;                                // smaller tree under the larger
        size[ra] += size[rb];
        --groups;
    }
    return groups - 1;
}

class Solution {
    private int[] parent, size;

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
        return x;
    }

    public int networkCables(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
        int groups = n;
        for (int[] c : connections) {
            int ra = find(c[0]), rb = find(c[1]);
            if (ra == rb) continue;
            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
            parent[rb] = ra;                            // smaller tree under the larger
            size[ra] += size[rb];
            groups--;
        }
        return groups - 1;
    }
}

function networkCables(n, connections) {
  if (connections.length < n - 1) return -1;          // n - 1 cables are needed
  const parent = Array.from({ length: n }, (_, i) => i);
  const size = new Array(n).fill(1);
  const find = x => {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
    return x;
  };
  let groups = n;
  for (const [a, b] of connections) {
    let ra = find(a), rb = find(b);
    if (ra === rb) continue;
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra;                                   // smaller tree under the larger
    size[ra] += size[rb];
    groups--;
  }
  return groups - 1;
}

fn solve(n: i64, connections: &[[i64; 2]]) -> i64 {
    let n = n as usize;
    if connections.len() + 1 < n {
        return -1;                                     // n - 1 cables are needed
    }
    let mut parent: Vec<usize> = (0..n).collect();
    let mut size = vec![1usize; n];
    fn find(parent: &mut Vec<usize>, mut x: usize) -> usize {
        while parent[x] != x {
            parent[x] = parent[parent[x]];             // path halving
            x = parent[x];
        }
        x
    }
    let mut groups = n as i64;
    for c in connections {
        let (mut ra, mut rb) = (find(&mut parent, c[0] as usize), find(&mut parent, c[1] as usize));
        if ra == rb {
            continue;
        }
        if size[ra] < size[rb] {
            std::mem::swap(&mut ra, &mut rb);
        }
        parent[rb] = ra;                               // smaller tree under the larger
        size[ra] += size[rb];
        groups -= 1;
    }
    groups - 1
}

import qualified Data.Map.Strict as M

-- A persistent union-find: parents in a map, union by size, finds follow parents to the root.
solve :: Int -> [[Int]] -> Int
solve n connections
  | length connections < n - 1 = -1                   -- n - 1 cables are needed
  | otherwise = go connections parent0 size0 n
  where
    parent0 = M.fromList [(i, i) | i <- [0 .. n - 1]]
    size0   = M.fromList [(i, 1 :: Int) | i <- [0 .. n - 1]]
    find p x = let y = p M.! x in if y == x then x else find p y
    go [] _ _ groups = groups - 1
    go ([a, b] : rest) p s groups
      | ra == rb  = go rest p s groups
      | sa < sb   = go rest (M.insert ra rb p) (M.insert rb (sa + sb) s) (groups - 1)
      | otherwise = go rest (M.insert rb ra p) (M.insert ra (sa + sb) s) (groups - 1)
      where
        ra = find p a
        rb = find p b
        sa = s M.! ra
        sb = s M.! rb
    go (_ : rest) p s groups = go rest p s groups

Variants to try

Return which cables to move: during the unions, record the cables whose ends were already in the same group.
Redundant connection: the first cable whose ends are already connected is the one that closes a cycle.
Minimum spanning tree: sort the edges by weight and add each one that joins two different groups (Kruskal).
Online queries mixed with new cables: the same structure answers each query in near-constant time.

Next problems

Medium15 min

Moving cables to connect a network

Examples

Constraints

Hints

Where people lose marks

Dry run on `7,[[0,1],[1,2],[2,0],[3,4],[4,5],[5,3]]`

How to think about it

The solution, in six languages

Variants to try

Next problems

The connection that closes a loop

Connect every point at the least cost

Count the islands in a grid

Keep going

The connection that closes a loop

Connect every point at the least cost

Count the islands in a grid

The pattern behind it

Moving cables to connect a network

Examples

Constraints

Hints

Where people lose marks

Dry run on 7,[[0,1],[1,2],[2,0],[3,4],[4,5],[5,3]]

How to think about it

The solution, in six languages

Variants to try

Next problems

The connection that closes a loop

Connect every point at the least cost

Count the islands in a grid

Keep going

The connection that closes a loop

Connect every point at the least cost

Count the islands in a grid

The pattern behind it

Dry run on `7,[[0,1],[1,2],[2,0],[3,4],[4,5],[5,3]]`