☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

Number of operations to make network connected

Hard TUF ID 515 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

There are n computers numbered 0 to n - 1 and a list connections where connections[i] = [a, b] is a cable between computers a and b. Any computer can reach any other computer that is connected to it directly or through other computers.

In one operation you may unplug an existing cable and plug it between any two computers that are not directly connected. Return the minimum number of operations needed to make every computer reachable from every other one, or -1 if it is impossible.

Constraints: 1 ≤ n ≤ 10^5, 0 ≤ connections.length ≤ min(n(n-1)/2, 10^5), no repeated cables, no cable from a computer to itself.

Example 1

n = 4, connections = [[0,1],[0,2],[1,2]]
answer = 1          // move cable 1-2 to join computer 3

Example 2

n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
answer = -1         // 6 computers need at least 5 cables; there are only 4

Example 3

n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
answer = 2          // {0,1,2,3}, {4}, {5}: two redundant cables, two joins needed

The key observation

Think of computers as vertices and cables as edges. The network falls into some number C of connected components. To merge C components into one, you need exactly C - 1 new links: each move joins two components, and no single move can join three. So the answer, when it exists, is C - 1.

Where does each moved cable come from? Not every cable can be moved for free. Unplugging a cable that is the only path between two halves of a component would split it, undoing the work. A cable is safe to move when its two ends are still connected without it, that is, when it closes a cycle inside its component. Call these extra (redundant) cables. The answer exists exactly when extra ≥ C - 1.

There is an even simpler way to state the feasibility test. A component with k computers needs k - 1 cables to stay connected, so the non-extra cables number n - C, and extra = m - (n - C) where m is the number of cables. Then extra ≥ C - 1 is the same as m - n + C ≥ C - 1, which is m ≥ n - 1. In words: if there are at least n - 1 cables in total, rearranging them always works; otherwise nothing works, since any connected graph on n vertices has at least n - 1 edges.

Both approaches below rely on this; they differ only in how they count components.

Approach 1: Count components with DFS

Intuition. Use the m ≥ n - 1 test first. If it passes, the answer is the number of components minus one, and counting components is a textbook traversal: start a DFS from every vertex that has not been visited yet; each such start discovers one new component.

Algorithm.

  1. If connections.length < n - 1, return -1.
  2. Build an adjacency list from the cables (both directions, since cables are undirected).
  3. For every vertex s not yet visited: increment components, then run an iterative DFS from s marking everything it reaches.
  4. Return components - 1.
static int dfsComponents(int n, int[][] connections) {
    if (connections.length < n - 1) return -1;          // fewer than n - 1 cables can never connect n machines
    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[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    int components = 0;
    for (int s = 0; s < n; s++) {
        if (visited[s]) continue;
        components++;
        visited[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                }
            }
        }
    }
    return components - 1;
}

Complexity. Time O(n + m): every vertex is pushed once and every cable is examined twice, once from each end. Space O(n + m) for the adjacency list, the visited array and the stack.

An explicit stack is used instead of recursion because a long chain of 10^5 computers would overflow the default Java call stack.

Approach 2: Disjoint Set (Union-Find)

Intuition. A Disjoint Set keeps a partition of the vertices into groups and answers two questions quickly: “which group is x in?” (find) and “merge the groups of a and b” (union). Process the cables one at a time:

After one pass we know both C (start at n and subtract each successful union) and extra, so we can apply the rule extra ≥ C - 1 directly. No adjacency list is needed at all, and the approach mirrors the reasoning in the key observation exactly.

The structure uses two standard optimisations. Union by size always hangs the smaller tree under the root of the larger one, so a tree of size s has height at most log2 s. Path compression makes every node on a find path point straight at the root, so later finds are almost free. Together they give an amortised cost of O(α(n)) per operation, where α is the inverse Ackermann function and never exceeds 4 for any realistic input.

static final class DisjointSet {
    final int[] parent, size;

    DisjointSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                         // already in the same set
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;                                    // hang the smaller tree under the larger
        size[ra] += size[rb];
        return true;
    }
}

Algorithm.

  1. Create a Disjoint Set of n singletons; set components = n and extra = 0.
  2. For each cable [a, b]: if union(a, b) succeeds, do components--; otherwise do extra++.
  3. Let needed = components - 1. Return needed if extra ≥ needed, else -1.
static int disjointSet(int n, int[][] connections) {
    DisjointSet ds = new DisjointSet(n);
    int components = n, extra = 0;
    for (int[] c : connections) {
        if (ds.union(c[0], c[1])) components--;            // cable joined two groups
        else extra++;                                      // cable inside one group: free to move
    }
    int needed = components - 1;
    return extra >= needed ? needed : -1;
}

Dry run on example 3, n = 6:

cable find(a), find(b) before result components extra
0-1 0, 1 merge 5 0
0-2 0, 2 merge 4 0
0-3 0, 3 merge 3 0
1-2 0, 0 same group 3 1
1-3 0, 0 same group 3 2

needed = 3 - 1 = 2 and extra = 2 ≥ 2, so the answer is 2.

Complexity. Time O(n + m · α(n)): initialisation is O(n) and each cable costs two near-constant find calls. Space O(n) for the parent and size arrays, which is less than the adjacency list of approach 1.

Which approach to prefer? Both are linear in practice. The Disjoint Set version is the one to remember for this family of problems because the edges can arrive one at a time (even as a stream) and it never needs the whole graph in memory.

Edge cases and pitfalls