Find minimum cable moves to connect all computers. Return -1 if not enough cables.
Input: n=4, connections=[[0,1],[0,2],[1,2]] → Output: 1
Input: n=6, connections=[[0,1],[0,2],[0,3],[1,2],[1,3]] → Output: 2
If cables < n-1, impossible. Otherwise count connected components - 1.
- If connections.length < n-1: return -1
- Union-Find to count connected components
- Answer = components - 1
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1;
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int components = n;
for (int[] c : connections) {
int ra = find(parent, c[0]), rb = find(parent, c[1]);
if (ra != rb) { parent[ra] = rb; components--; }
}
return components - 1;
}
private int find(int[] parent, int x) {
return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}
- Time Complexity: O(n * alpha(n))
- Space Complexity: O(n)