Minimum Operations to Make Network Connected - Visualization

Graphs

Contents

ProblemExamplesSolutionAlgorithmCode

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❯

  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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

// Function to find the root parent of a node with path compression
int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

// Function to union two sets
int unionSets(int parent[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);
    if (rootX != rootY) {
        parent[rootY] = rootX;
        return 1; // Union done
    }
    return 0; // Already connected
}

int makeConnected(int n, int connections[][2], int m) {
    if (m < n - 1) return -1; // Not enough edges

    int parent[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    int components = n;
    for (int i = 0; i < m; i++) {
        if (unionSets(parent, connections[i][0], connections[i][1])) {
            components--;
        }
    }

    return components - 1;
}

int main() {
    int connections1[][2] = {{0,1},{0,2},{1,2}};
    int result1 = makeConnected(4, connections1, 3);
    printf("%d\n", result1); // Output: 1

    int connections2[][2] = {{0,1},{0,2},{0,3},{1,4}};
    int result2 = makeConnected(6, connections2, 4);
    printf("%d\n", result2); // Output: -1

    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...