Number of Operations to Make Network Connected

Medium
453.

Number of Operations to Make Network Connected

Number of Operations to Make Network Connected is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Microsoft interviews.

There are n computers numbered 0 through n - 1 joined by ethernet cables; connections[i] = [a, b] connects computers a and b.

You may unplug any cable and use it to connect a different pair. Return the minimum number of such moves that makes every computer reachable from every other, or -1 if it is impossible.

Example 1

Input
n = 4, connections = [[0,1],[0,2],[1,2]]
Output
1

Example 2

Input
n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output
2

Example 3

Input
n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output
-1
Explanation
Only four cables for six computers.

Constraints

  • 1 <= n <= 40
  • 0 <= connections.length <= 60
  • There are no duplicate connections and no self-loops.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var makeConnected = function(n, connections) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Operations to Make Network Connected — Solution

Number of Operations to Make Network Connected solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Operations to Make Network Connected is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Microsoft interviews.

Problem statement

There are n computers numbered 0 through n - 1 joined by ethernet cables; connections[i] = [a, b] connects computers a and b.

You may unplug any cable and use it to connect a different pair. Return the minimum number of such moves that makes every computer reachable from every other, or -1 if it is impossible.

Example 1

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1

Example 2

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2

Example 3

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: Only four cables for six computers.

Constraints

  • 1 <= n <= 40
  • 0 <= connections.length <= 60
  • There are no duplicate connections and no self-loops.

Hints for Number of Operations to Make Network Connected

  1. Hint 1

    Connecting n computers needs at least n - 1 cables — fewer than that is impossible.

  2. Hint 2

    With enough cables, every redundant one inside a component can be moved somewhere useful.

  3. Hint 3

    Count the connected components with union-find; the answer is components - 1.

How to solve Number of Operations to Make Network Connected

With at least n - 1 cables it is always possible, and each move can join two components, so the answer is components - 1.

Approach

  1. Return -1 if len(connections) < n - 1.
  2. Union-find to count components.
  3. Return components - 1.

Why it works

Joining c components requires c - 1 new links; each redundant cable inside a component can be moved to provide one, and having ≥ n - 1 cables guarantees enough redundancy.

Complexity

  • Time — O((n + e) · α(n))
  • Space — O(n)

Pitfalls

  • The cable-count check is what makes the component count sufficient.

Reference solution

Python

def makeConnected(n: int, connections) -> int:
    if len(connections) < n - 1:
        return -1
    parent = list(range(n))

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

    components = n
    for a, b in connections:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            components -= 1
    return components - 1

Java

private static int findRoot(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

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[] e : connections) {
        int a = findRoot(parent, e[0]);
        int b = findRoot(parent, e[1]);
        if (a != b) {
            parent[a] = b;
            components--;
        }
    }
    return components - 1;
}

C++

static int findRoot(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int makeConnected(int n, vector<vector<int>>& connections) {
    if ((int) connections.size() < n - 1) return -1;
    vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    int components = n;
    for (const auto& e : connections) {
        int a = findRoot(parent, e[0]);
        int b = findRoot(parent, e[1]);
        if (a != b) {
            parent[a] = b;
            components--;
        }
    }
    return components - 1;
}

JavaScript

var makeConnected = function(n, connections) {
    if (connections.length < n - 1) return -1;
    const parent = [];
    for (let i = 0; i < n; i++) parent.push(i);
    const find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    let components = n;
    for (let i = 0; i < connections.length; i++) {
        const a = find(connections[i][0]);
        const b = find(connections[i][1]);
        if (a !== b) {
            parent[a] = b;
            components--;
        }
    }
    return components - 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)