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.

Examples❯

n	Edges	Output	Description
4	[[0,1],[0,2],[1,2]]	1	We can remove the edge [1,2] and use it to connect node 3
6	[[0,1],[0,2],[0,3],[1,4]]	-1	Not enough edges to connect all components
5	[[0,1],[0,2],[3,4],[2,3],[2,4]]	0	The network is already connected
3	[[0,1],[1,2],[2,0]]	0	All nodes form a cycle and are already connected
4	[[0,1]]	-1	Only 1 edge is not enough to connect 4 nodes

Solution❯

To solve this problem, we need to ensure that the entire graph (network) becomes a single connected component using the minimum number of edge rearrangements.

Key Observations:

To connect n nodes, we need at least n - 1 edges.
If we have fewer than n - 1 edges, it is impossible to connect all nodes — return -1.
If we have enough edges, we can count how many connected components the graph has. If there are c components, we need at least c - 1 operations to connect them all.

Steps:

Check if number of edges < n - 1. If true, return -1.
Use DFS or Union-Find to count the number of connected components.
The answer is components - 1, since connecting all components requires one less operation than their total number.

Algorithm Steps❯

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

Code

JavaScript

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

⬅ Previous TopicKruskal's Algorithm - Minimum Spanning Tree

Next Topic ⮕Most Stones Removed with Same Row or Column