Making wired Connections

The problem, simply

There are n computers, numbered 0 to n - 1, and a list of cables. Each cable joins two computers. A computer can talk to another if there is a chain of cables between them.

In one move you can unplug any cable and plug it between any two computers. Find the fewest moves so that every computer can talk to every other one. If it can never work, return -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Two facts solve it.

• Joining n computers needs at least n - 1 cables. With fewer, return -1.
• With enough cables, the spare ones always exist where you need them. So the answer is the number of separate groups minus 1.

Count the groups with breadth first search: start a search from every computer that no search has reached yet, and count the searches.

import java.util.*;

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;          // not enough cable
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] c : connections) {
            adj.get(c[0]).add(c[1]);
            adj.get(c[1]).add(c[0]);
        }
        boolean[] seen = new boolean[n];
        int groups = 0;
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            groups++;                                        // a new group starts here
            Queue<Integer> line = new ArrayDeque<>();
            line.add(s);
            seen[s] = true;
            while (!line.isEmpty()) {
                int u = line.poll();
                for (int v : adj.get(u)) {
                    if (!seen[v]) { seen[v] = true; line.add(v); }
                }
            }
        }
        return groups - 1;
    }
}

How long it takes: every computer and every cable is touched a constant number of times, O(V + E). Extra room: the neighbour lists, O(V + E).

Way 2: the clever way

Same two facts, but count groups with team captains (union find), so we never build neighbour lists. Each computer has a parent; follow parents to reach the group's captain.

1. If there are fewer than n - 1 cables, return -1.
2. Start with n groups, each computer its own captain.
3. For each cable, find the captains of both ends. If they differ, join them and do groups--. If they are the same, the cable is spare.
4. Return groups - 1.

class Solution {
    private int[] parent, rank;

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // point straight at the captain
        return parent[x];
    }

    private boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                         // already connected: spare cable
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }

    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;         // not enough cable
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int groups = n;
        for (int[] c : connections) {
            if (union(c[0], c[1])) groups--;
        }
        return groups - 1;
    }
}

How long it takes: each cable costs an almost constant find and union, so about O(V + E). Extra room: only the parent and rank arrays, O(V).

Watch out for

• Why are the spares always enough? A group of k computers with c cables has c - (k - 1) spares. Add that over all groups: total spares = E - (n - groups). If E >= n - 1, that is at least groups - 1.
• Returning the number of groups instead of groups - 1. One group needs zero moves.
• Duplicate cables between the same two computers. They are spare, and union find handles them for free.
• Deep recursion in find. With union by rank the chains stay short, so recursion is safe here.

What interviewers ask next

• Which cables should move? Every cable whose union returned false is spare. Join the captains of the groups one after another using those cables.
• Number of provinces or friend circles (LeetCode 547)? The same group counting, without the cable check.
• Cables have different prices and you want the cheapest network? That is a minimum spanning tree: Kruskal's algorithm.
• Can you do it with depth first search? Yes, any search that counts groups works. Union find is handy because it needs no neighbour lists and handles cables arriving one by one.

Remember this

Grown-up words: computers are vertices, cables are edges, groups are connected components, spare cables are redundant edges that close a cycle, team captains are union find roots, and n - 1 is the number of edges in a spanning tree.