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.
Input: n=4, connections=[[0,1],[0,2],[1,2]] → Output: 1Input: n=6, connections=[[0,1],[0,2],[0,3],[1,2],[1,3]] → Output: 2
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.
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)