28 · Union-Find & Minimum Spanning Trees

#1319 Number of Operations to Make Network Connected

frequently reported atAmazon

the problem

In plain words

n computers (0..n−1) are joined by ethernet cables connections[i] = [a, b]. In one operation you may unplug any cable and plug it between two computers. Return the minimum number of operations to connect all computers, or -1 if impossible.

in n = 4, connections = [[0,1],[0,2],[1,2]]

out 1

Move cable 1–2 to join computer 3.

in n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]

out 2

Two spare cables (1–2 and 1–3) bring in computers 4 and 5.

in n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]

out -1

Only 4 cables; 6 computers need at least 5.

1 ≤ n ≤ 10⁵
1 ≤ connections.length ≤ min(n(n−1)/2, 10⁵)
No repeated connections

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternUnion-Find (DSU)Graph DFS / BFS traversal

Fewer than n − 1 cables → impossible. Otherwise there are always enough spare cables, and joining c components needs exactly c − 1 moves.

solutions

From brute force to optimal

If cables ≥ n − 1, the answer is (number of components) − 1. Count them with an iterative DFS.

Return -1 if connections.length < n − 1.
Build adjacency lists.
Count DFS starts; return count − 1.

timeO(n + m)

Every node and cable is visited once (m = cables).

spaceO(n + m)

Adjacency lists, seen, and the stack.

javajava.util.*

1class Solution {2    public int makeConnected(int n, int[][] connections) {3        if (connections.length < n - 1) return -1; // not enough cables, whatever we do4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());6        for (int[] c : connections) {7            adj.get(c[0]).add(c[1]);8            adj.get(c[1]).add(c[0]);9        }10        boolean[] seen = new boolean[n];11        int components = 0;12        for (int i = 0; i < n; i++) {13            if (seen[i]) continue;14            components++;15            ArrayDeque<Integer> stack = new ArrayDeque<>();16            stack.push(i);17            seen[i] = true;18            while (!stack.isEmpty()) {19                int u = stack.pop();20                for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; stack.push(v); }21            }22        }23        return components - 1; // one cable joins two components24    }25}

components = n; each cable that merges two different sets does components--.

Return -1 if connections.length < n − 1.
Union every cable, counting real merges.
Return components − 1.

timeO(n + m·α(n))

O(n) to initialise, near-constant per cable.

spaceO(n)

parent and size only — no adjacency lists needed.

javajava.util.*

1class Solution {2    private int[] parent, size;3 4    private int find(int x) {5        if (parent[x] != x) parent[x] = find(parent[x]);6        return parent[x];7    }8 9    public int makeConnected(int n, int[][] connections) {10        if (connections.length < n - 1) return -1;11        parent = new int[n];12        size = new int[n];13        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }14        int components = n;15        for (int[] c : connections) {16            int ra = find(c[0]), rb = find(c[1]);17            if (ra == rb) continue;            // a spare (redundant) cable18            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }19            parent[rb] = ra;20            size[ra] += size[rb];21            components--;22        }23        return components - 1;24    }25}

in the room

How to say it in the interview

talk track

Prove the spare-cable claim: with m ≥ n − 1 cables and c components, a spanning forest uses n − c cables, leaving m − (n − c) ≥ c − 1 spares.

traps

Returning the number of components — c components need only c − 1 moves.
Returning the number of spare cables: spares only prove it's possible; the answer is still c − 1.
Recursive DFS on a 10⁵-node chain can overflow the stack. Use DSU or an explicit stack.

what they ask next

Follow-ups

Which cables should you move?

Every cable whose union failed is a spare. Take one spare per extra component and use it to join that component to the first one.

What if you can't move cables, only buy new ones?

Then it's never impossible: you buy exactly c − 1 new cables, one per extra component.

before you submit

Edge cases to test

Exactly n − 1 cables but some sit inside one cluster → still possible, the spares get moved.
Already connected → 0 moves.
One cable short of n − 1 → -1, without looking at the graph at all.
n up to 10⁵: a recursive DFS can overflow the stack on a long chain — prefer DSU or an explicit stack.

practise next