Minimum Operations
to Make Network Connected

Problem Statement

You are given a network of n computers numbered from 0 to n-1, connected by a list of m edges. Each edge connects two computers directly. In one operation, you can remove any existing edge and reconnect it between any two disconnected computers.

Your task is to determine the minimum number of such operations required to ensure that all computers are directly or indirectly connected. If it is not possible to connect the entire network, return -1.

Algorithm Steps

1. If number of edges < n - 1, return -1 — not enough edges to connect the graph.
2. Initialize n nodes and mark them unvisited.
3. Use DFS or Union-Find to count the number of connected components c.
4. Return c - 1 as the minimum number of operations required.

Code

function makeConnected(n, connections) {
  if (connections.length < n - 1) return -1; // Not enough edges

  const parent = Array.from({ length: n }, (_, i) => i);

  function find(x) {
    if (parent[x] !== x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  function union(x, y) {
    const rootX = find(x);
    const rootY = find(y);
    if (rootX !== rootY) {
      parent[rootY] = rootX;
      return true;
    }
    return false;
  }

  let components = n;
  for (const [a, b] of connections) {
    if (union(a, b)) {
      components--;
    }
  }

  return components - 1;
}

console.log(makeConnected(4, [[0,1],[0,2],[1,2]])); // 1
console.log(makeConnected(6, [[0,1],[0,2],[0,3],[1,4]])); // -1