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❯

Understanding the Problem

We are given n computers labeled from 0 to n - 1 and a list of connections where each connection connects two computers directly. Our goal is to determine the minimum number of operations required to make the entire network connected — meaning every computer can reach every other computer, either directly or indirectly.

In each operation, we are allowed to rewire an existing connection — that is, remove one connection and place it between any two disconnected computers. The challenge is to determine whether this is possible and if so, what the minimum number of such operations is.

Step-by-Step Solution with Example

Step 1: Basic Requirement Check

To connect n computers, we must have at least n - 1 connections. This is a fundamental rule in graph theory: to connect n nodes in a single connected component without cycles, you need at least n - 1 edges.

So, if the number of connections is less than n - 1, we immediately return -1 because it's impossible to connect all computers.

Step 2: Count Connected Components

If we have at least n - 1 edges, then it's possible — but we still need to figure out how many disconnected parts (components) are present in the network.

We can use either Depth-First Search (DFS) or the Union-Find (Disjoint Set Union) algorithm to count how many separate connected components exist in the network.

Step 3: Calculate Operations Needed

If there are c connected components, then we need at least c - 1 operations to connect them all. This is because each operation can connect two components into one. So if we have 3 components, we need 2 operations to make them into 1.

Step 4: Work Through Example

Let's say n = 6 and the connections are:


[[0,1], [0,2], [0,3], [1,4]]

This is 4 connections, but we need at least 6 - 1 = 5 connections. Since we have only 4, it’s impossible to connect all 6 computers. We return -1.

Now, consider another example:


n = 6
connections = [[0,1], [0,2], [0,3], [1,4], [2,5]]

Here, we have 5 connections which is exactly n - 1. We run Union-Find or DFS and see all computers are connected — so only 1 component exists. No operations needed. We return 0.

Edge Cases

Not Enough Edges: If the number of connections is less than n - 1, we must return -1 right away — impossible case.
Already Connected: If the network is already a single connected component, no operations are required — return 0.
Multiple Disconnected Components: Count the components and return components - 1 as the number of needed operations.

Finally

This problem is a classic application of graph connectivity. The key insight is recognizing that to fully connect a network of n computers, you need at least n - 1 edges. Once that condition is met, counting connected components helps determine how many rearrangements are needed.

Always begin by validating input constraints (like number of edges), then apply a graph traversal algorithm to understand the structure of the network.

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

Comments

Loading comments...