Number of Operations to Make Network Connected

Medium Graphs Connected Components Original on LeetCode

Reported atUberInMobi

Number of Operations to Make Network Connected is a medium graphs problem solved with the connected components pattern. The best approach, optimal (union-find), runs in O(n + m · α(n)) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dfs component count) up.

Problem

A data centre has n machines numbered 0 to n - 1. You are given connections, where connections[i] = [a, b] means a network cable directly links machines a and b. Two machines can talk if there is a path of cables between them.

In one operation you may unplug any existing cable and plug it back in between any two machines that are currently not linked by a cable. Return the minimum number of operations needed so that every machine can reach every other machine, or -1 if that is impossible.

Examples

Example 1

Input
n = 5, connections = [[0,1],[1,2],[2,0],[3,4]]
Output
1
Why
The cable 2-0 is redundant inside the triangle 0-1-2; move it to join 0 with 3.

Example 2

Input
n = 6, connections = [[0,1],[0,2],[1,2],[3,4]]
Output
-1
Why
Six machines need at least five cables, but only four exist.

Example 3

Input
n = 4, connections = [[0,1],[1,2],[2,3]]
Output
0
Why
The machines already form one chain, so nothing has to move.

Constraints

  • 1 <= n <= 10^5
  • 1 <= connections.length <= min(n * (n - 1) / 2, 10^5)
  • connections[i] = [a, b] with 0 <= a, b < n and a != b.
  • No pair of machines is joined by more than one cable.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (DFS component count)O(n + m)O(n + m)
Optimal (union-find)O(n + m · α(n))O(n)

1Brute force (DFS component count)

TimeO(n + m)Every machine and every cable is visited a constant number of times (m = number of cables).
SpaceO(n + m)The adjacency list stores each cable twice; the stack and visited array are O(n).

Build an adjacency list, count connected components with an iterative DFS, and answer components - 1 (or -1 if there are fewer than n - 1 cables).

  1. If connections.length < n - 1, return -1.
  2. Build the adjacency list from the cables.
  3. For every unvisited machine, start a DFS that marks its whole component and add one to the count.
  4. Return count - 1.
class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        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 components = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            components++;
            seen[s] = true;
            stack.push(s);
            while (!stack.isEmpty()) {
                int u = stack.pop();
                for (int v : adj.get(u)) {
                    if (!seen[v]) {
                        seen[v] = true;
                        stack.push(v);
                    }
                }
            }
        }
        return components - 1;
    }
}

2Optimal (union-find)

TimeO(n + m · α(n))Each find is nearly constant with path compression and union by size.
SpaceO(n)Only the parent and size arrays; no adjacency list is built.

Start with n separate sets. Each cable that joins two different sets merges them and reduces the component count by one; cables inside one set are spare. With enough cables, the answer is components - 1.

  1. If connections.length < n - 1, return -1.
  2. Initialise parent[i] = i and components = n.
  3. For each cable, find both roots (with path compression); if they differ, union them by size and decrement components.
  4. Return components - 1.
class Solution {
    private int[] parent, size;

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

    public int makeConnected(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 components = n;
        for (int[] c : connections) {
            int a = find(c[0]), b = find(c[1]);
            if (a == b) continue;
            if (size[a] < size[b]) { int t = a; a = b; b = t; }
            parent[b] = a;
            size[a] += size[b];
            components--;
        }
        return components - 1;
    }
}

Edge cases to test

  • Fewer than n - 1 cables: impossible no matter how they are moved
  • A single machine: already connected, answer 0
  • Machines that appear in no cable at all (isolated components)
  • Many cables inside one component and many isolated machines

Hints

Hint 1

A connected network on n machines needs at least n - 1 cables. If there are fewer, the answer is -1.

Hint 2

If there are enough cables, every extra cable inside a component can be moved. Joining c components takes exactly c - 1 moves.

Hint 3

So the whole problem reduces to counting connected components: use DFS/BFS or a disjoint set union.

FAQ

What is the best time complexity for Number of Operations to Make Network Connected?

Optimal (union-find) runs in O(n + m · α(n)) time and O(n) extra space. Each find is nearly constant with path compression and union by size.

Which pattern does Number of Operations to Make Network Connected use?

It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.

Is there a brute force solution for Number of Operations to Make Network Connected?

Yes. Brute force (DFS component count) takes O(n + m) time and O(n + m) space. Build an adjacency list, count connected components with an iterative DFS, and answer components - 1 (or -1 if there are fewer than n - 1 cables).

Which edge cases should I test for Number of Operations to Make Network Connected?

Fewer than n - 1 cables: impossible no matter how they are moved; A single machine: already connected, answer 0; Machines that appear in no cable at all (isolated components); Many cables inside one component and many isolated machines.