ProgramGuru

Minimum Operations to Make Network Connected

Problem and examples

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.

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

How it works

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
    vector<int> parent;
public:
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    bool unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
            return true;
        }
        return false;
    }
};

int makeConnected(int n, vector<vector<int>> &connections) {
    if (connections.size() < n - 1) return -1;

    UnionFind uf(n);
    int components = n;

    for (auto &edge : connections) {
        if (uf.unionSets(edge[0], edge[1])) {
            components--;
        }
    }

    return components - 1;
}

int main() {
    vector<vector<int>> connections1 = {{0,1},{0,2},{1,2}};
    cout << makeConnected(4, connections1) << endl; // 1

    vector<vector<int>> connections2 = {{0,1},{0,2},{0,3},{1,4}};
    cout << makeConnected(6, connections2) << endl; // -1

    return 0;
}

Python implementation

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    if rootX != rootY:
        parent[rootY] = rootX
        return True
    return False

def makeConnected(n, connections):
    if len(connections) < n - 1:
        return -1

    parent = list(range(n))
    components = n

    for a, b in connections:
        if union(parent, a, b):
            components -= 1

    return components - 1


print(makeConnected(4, [[0,1],[0,2],[1,2]]))  # Output: 1
print(makeConnected(6, [[0,1],[0,2],[0,3],[1,4]]))  # Output: -1

Java implementation

public class NetworkConnectivity {

    public static int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    public static boolean union(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
            return true;
        }
        return false;
    }

    public static 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[] edge : connections) {
            if (union(parent, edge[0], edge[1])) {
                components--;
            }
        }

        return components - 1;
    }

    public static void main(String[] args) {
        int[][] connections1 = {{0,1},{0,2},{1,2}};
        System.out.println(makeConnected(4, connections1)); // 1

        int[][] connections2 = {{0,1},{0,2},{0,3},{1,4}};
        System.out.println(makeConnected(6, connections2)); // -1
    }
}

JavaScript implementation

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

Go implementation

package main

import "fmt"

func find(parent []int, x int) int {
    if parent[x] != x {
        parent[x] = find(parent, parent[x])
    }
    return parent[x]
}

func union(parent []int, x, y int) bool {
    rootX := find(parent, x)
    rootY := find(parent, y)
    if rootX != rootY {
        parent[rootY] = rootX
        return true
    }
    return false
}

func makeConnected(n int, connections [][]int) int {
    if len(connections) < n-1 {
        return -1
    }

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

    components := n
    for _, edge := range connections {
        if union(parent, edge[0], edge[1]) {
            components--
        }
    }

    return components - 1
}

func main() {
    fmt.Println(makeConnected(4, [][]int{{0,1},{0,2},{1,2}})) // 1
    fmt.Println(makeConnected(6, [][]int{{0,1},{0,2},{0,3},{1,4}})) // -1
}

Rust implementation

fn find(parent: &mut Vec<usize>, x: usize) -> usize {
    if parent[x] != x {
        parent[x] = find(parent, parent[x]);
    }
    parent[x]
}

fn union(parent: &mut Vec<usize>, x: usize, y: usize) -> bool {
    let root_x = find(parent, x);
    let root_y = find(parent, y);
    if root_x != root_y {
        parent[root_y] = root_x;
        true
    } else {
        false
    }
}

fn make_connected(n: usize, connections: &Vec<Vec<usize>>) -> i32 {
    if connections.len() < n - 1 {
        return -1;
    }

    let mut parent: Vec<usize> = (0..n).collect();
    let mut components = n;

    for edge in connections {
        if union(&mut parent, edge[0], edge[1]) {
            components -= 1;
        }
    }

    (components - 1) as i32
}

fn main() {
    let connections1 = vec![vec![0,1], vec![0,2], vec![1,2]];
    println!("{}", make_connected(4, &connections1)); // 1

    let connections2 = vec![vec![0,1], vec![0,2], vec![0,3], vec![1,4]];
    println!("{}", make_connected(6, &connections2)); // -1
}

Kotlin implementation

fun find(parent: IntArray, x: Int): Int {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x])
    }
    return parent[x]
}

fun union(parent: IntArray, x: Int, y: Int): Boolean {
    val rootX = find(parent, x)
    val rootY = find(parent, y)
    if (rootX != rootY) {
        parent[rootY] = rootX
        return true
    }
    return false
}

fun makeConnected(n: Int, connections: Array<IntArray>): Int {
    if (connections.size < n - 1) return -1

    val parent = IntArray(n) { it }
    var components = n
    for (edge in connections) {
        if (union(parent, edge[0], edge[1])) {
            components--
        }
    }

    return components - 1
}

fun main() {
    val connections1 = arrayOf(intArrayOf(0,1), intArrayOf(0,2), intArrayOf(1,2))
    println(makeConnected(4, connections1)) // 1

    val connections2 = arrayOf(intArrayOf(0,1), intArrayOf(0,2), intArrayOf(0,3), intArrayOf(1,4))
    println(makeConnected(6, connections2)) // -1
}

Swift implementation

func find(_ parent: inout [Int], _ x: Int) -> Int {
    if parent[x] != x {
        parent[x] = find(&parent, parent[x])
    }
    return parent[x]
}

func union(_ parent: inout [Int], _ x: Int, _ y: Int) -> Bool {
    let rootX = find(&parent, x)
    let rootY = find(&parent, y)
    if rootX != rootY {
        parent[rootY] = rootX
        return true
    }
    return false
}

func makeConnected(_ n: Int, _ connections: [[Int]]) -> Int {
    if connections.count < n - 1 { return -1 }

    var parent = Array(0..<n)
    var components = n

    for edge in connections {
        if union(&parent, edge[0], edge[1]) {
            components -= 1
        }
    }

    return components - 1
}

print(makeConnected(4, [[0,1],[0,2],[1,2]])) // 1
print(makeConnected(6, [[0,1],[0,2],[0,3],[1,4]])) // -1

TypeScript implementation

function makeConnected(n: number, connections: number[][]): number {
  if (connections.length < n - 1) return -1;

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

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

  function union(x: number, y: number): boolean {
    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