Network Connected (Union Find variant)

Share

Given n computers and connections, use Union-Find to count cables that can be reused and determine if connecting all computers is possible.

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]] → Output: -1

Solution Approach

Union-Find: union all connected nodes. Count redundant edges (same component). If redundant >= components-1, return components-1. Otherwise -1.

  • If edges < n-1: impossible, return -1.
  • For each edge: if same component, it is redundant. Else union.
  • Count 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)