Number of Operations to Make Network Connected

Share

Find minimum cable moves to connect all computers. Return -1 if not enough cables.

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 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
Java
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)