Number of Operations to Make Network Connected

Share

Given n computers and connections, find the minimum number of operations needed to connect all computers. In one operation, you can disconnect any existing cable and connect two unconnected computers.

Example 1
Input: n=4, connections=[[0,1],[0,2],[1,2]] → Output: 1
Example 2
Input: n=6, connections=[[0,1],[0,2],[0,3],[1,2],[1,3]] → Output: 2

Solution Approach

If connections < n-1, impossible (return -1). Otherwise, use Union-Find to count components. Need (components-1) operations.

  • If edges < n-1: return -1.
  • Union-Find: process all edges, union nodes.
  • Count distinct components = number of i where find(i)==i.
  • Return components - 1.
Java
class Solution {
    int[] parent;
    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 components = n;
        for (int[] c : connections) {
            int pu = find(c[0]), pv = find(c[1]);
            if (pu != pv) { parent[pu] = pv; components--; }
        }
        return components - 1;
    }
    private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
}
  • Time Complexity: O(N + E * alpha(N))
  • Space Complexity: O(N)