Number of Operations to Make Network Connected

medium graph union find

Problem

There are n computers numbered 0..n-1 and a list of connections where connections[i] = [a, b] is a cable. You may remove a cable and reattach it between any two computers. Return the minimum number of moves to make every computer reachable from every other, or -1 if impossible.

Inputn = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]

Output2

Two cables are redundant; we have 3 components, needing 2 moves to merge them.

connections (JSON)

def make_connected(n, connections):
    if len(connections) < n - 1: return -1
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    comps = n
    for a, b in connections:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            comps -= 1
    return comps - 1

function makeConnected(n, connections) {
  if (connections.length < n - 1) return -1;
  const parent = Array.from({ length: n }, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
  }
  let comps = n;
  for (const [a, b] of connections) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) { parent[ra] = rb; comps--; }
  }
  return comps - 1;
}

class Solution {
    int[] parent;
    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];
        for (int i = 0; i < n; i++) parent[i] = i;
        int comps = n;
        for (int[] e : connections) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra != rb) { parent[ra] = rb; comps--; }
        }
        return comps - 1;
    }
}

class Solution {
public:
    vector<int> parent;
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        if ((int)connections.size() < n - 1) return -1;
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        int comps = n;
        for (auto& e : connections) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra != rb) { parent[ra] = rb; comps--; }
        }
        return comps - 1;
    }
};

Explanation

The big realization is that you only ever need to move spare cables. A cable is spare when it connects two computers that are already linked through other cables. So the real question becomes: how many separate groups of computers are there, and do we have enough spare cables to join them?

First a quick check: to connect n computers you need at least n - 1 cables. If there are fewer than that, it is impossible, so we return -1.

We use union-find to count connected groups (components). Start with comps = n (every computer alone). For each cable, if its two endpoints have different roots we union them and do comps--. If they already share a root, the cable was redundant.

At the end we have comps separate groups. Joining them into one needs exactly comps - 1 moves, and the extra cables guarantee we have enough to spare, so the answer is comps - 1.

Example: n = 6, connections [[0,1],[0,2],[0,3],[1,2],[1,3]]. Those edges merge {0,1,2,3} into one group, leaving 4 and 5 alone — 3 components. Answer is 3 - 1 = 2.

Time: O((n + m) · α(n)) Space: O(n)