Given n computers and connections, use Union-Find to count cables that can be reused and determine if connecting all computers is possible.
Input: n=4, connections=[[0,1],[0,2],[1,2]] → Output: 1Input: n=6, connections=[[0,1],[0,2],[0,3],[1,2]] → Output: -1
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.
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)