Leetcode 1319. Number of Operations to Make Network Connected

Problem Description

The problem we have at hand is that of connecting a network of computers. We have a total of n computers, numbered from 0 to n-1. These computers are connected together by ethernet cables, forming a network. In this network, there are certain direct connections between computers, and some computers are indirectly connected through other computers.

Our task is to make all the computers directly connected to each other. To achieve this, we can perform a certain operation: we can remove a cable that directly connects two computers and use it to directly connect two previously disconnected computers. We need to determine the minimum number of times we need to perform this operation to connect all the computers. If it is not possible to connect all computers, we return -1.

To better understand this problem, let's consider an example:

Example:

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

Here, we have 4 computers (0, 1, 2, and 3). The connections are such that computer 0 is directly connected to computers 1 and 2, and computer 1 is directly connected to computer 2. Computer 3 is disconnected.

A possible solution is to remove the cable between computers 1 and 2 (as they are both connected to computer 0) and use it to connect computer 1 and 3. Now, all four computers are connected directly or indirectly. We needed to perform the operation only once, hence the output is 1.

Solution Approach

The solution is based on depth-first search (DFS) and graph theory. A minimum of n-1 cables are necessary to connect n computers. If there are fewer cables, we cannot connect all computers and return -1. Otherwise, we count the number of connected components in the network. To connect these, we need to perform number_of_connected_components - 1 operations (each operation connects two components), hence that is the output of the algorithm.

The steps of the solution are as follows:

1. Check if there are enough connections. If not, return -1.
2. Build a graph based on the connections array.
3. Perform a DFS starting from each node to find all connected components of the graph.
4. Return the number of components - 1.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int makeConnected(int n, vector<vector<int>>& connections) {
6    // To connect n nodes, we need at least n - 1 edges
7    if (connections.size() < n - 1)
8      return -1;
9
10    int numOfConnected = 0;
11    vector<vector<int>> graph(n);
12    unordered_set<int> seen;
13
14    // Build the graph
15    for (const vector<int>& conn : connections) {
16      graph[conn[0]].push_back(conn[1]);
17      graph[conn[1]].push_back(conn[0]);
18    }
19
20    // DFS to find connected components
21    for (int i = 0; i < n; ++i)
22      if (seen.insert(i).second) {
23        dfs(graph, i, seen);
24        ++numOfConnected;
25      }
26
27    // Return number of operations needed to connect components (number of components - 1)
28    return numOfConnected - 1;
29  }
30
31 private:
32  // DFS helper function
33  void dfs(const vector<vector<int>>& graph, int u, unordered_set<int>& seen) {
34    for (const int v : graph[u])
35      if (seen.insert(v).second)
36        dfs(graph, v, seen);
37  }
38};

Python Solution

Python is a flexible and easy-to-understand programming language which can be used to solve this problem.

Here is how you can implement it in Python:

1
2python
3from collections import defaultdict
4
5def makeConnected(n, connections):
6    if len(connections) < n - 1:
7        return -1
8
9    graph = defaultdict(list)
10    seen = set()
11    numOfConnected = 0
12
13    # Build the graph
14    for conn in connections:
15        graph[conn[0]].append(conn[1])
16        graph[conn[1]].append(conn[0])
17
18    # DFS to find connected components
19    for i in range(n):
20        if i not in seen:
21            dfs(graph, i, seen)
22            numOfConnected += 1
23
24    # Return number of needed operations to connect all components
25    return numOfConnected - 1
26
27def dfs(graph, node, seen):
28    seen.add(node)
29    for neighbour in graph[node]:
30        if neighbour not in seen:
31            dfs(graph, neighbour, seen)

Javascript Solution

You can use Javascript to solve the problem. Here is the solution in Javascript:

1
2javascript
3function makeConnected(n, connections) {
4    if (connections.length < n - 1) {
5        return -1;
6    }
7
8    let graph = new Array(n).fill(0).map(() => new Array());
9    let seen = new Set();
10    let numOfConnected = 0;
11
12    // Build the graph
13    for (let conn of connections) {
14        graph[conn[0]].push(conn[1]);
15        graph[conn[1]].push(conn[0]);
16    }
17
18    // DFS to find connected components
19    for (let i = 0; i < n; i++) {
20        if (!seen.has(i)) {
21            dfs(graph, i, seen);
22            numOfConnected++;
23        }
24    }
25
26    // Return number of operations needed to connect components
27    return numOfConnected - 1;
28}
29
30function dfs(graph, node, seen) {
31    seen.add(node);
32    for (let neighbour of graph[node]) {
33        if (!seen.has(neighbour)) {
34            dfs(graph, neighbour, seen);
35        }
36    }
37}

Java Solution

Java is also a popular choice for interview problems due to its strong object-oriented programming features and versatility. Here's a solution in Java:

1
2java
3import java.util.*;
4
5class Solution {
6    public int makeConnected(int n, List<List<Integer>> connections) {
7        if (connections.size() < n - 1) 
8            return -1;
9
10        List<Integer>[] graph = new ArrayList[n];
11        Set<Integer> seen = new HashSet<>();
12        int numOfConnected = 0;
13
14        // Build the graph
15        for (int i = 0; i < n; i++) 
16            graph[i] = new ArrayList<>();
17        
18        for (List<Integer> conn : connections) {
19            graph[conn.get(0)].add(conn.get(1));
20            graph[conn.get(1)].add(conn.get(0));
21        }
22
23        // DFS to find connected components
24        for (int i = 0; i < n; i++) {
25            if (seen.add(i)) {
26                dfs(graph, i, seen);
27                numOfConnected++;
28            }
29        }
30
31        // Return number of operations needed to connect components
32        return numOfConnected - 1;
33    }
34
35    // DFS helper function
36    private void dfs(List<Integer>[] graph, int node, Set<Integer> seen) {
37        for (int neighbour : graph[node]) {
38            if (seen.add(neighbour)) 
39                dfs(graph, neighbour, seen);
40        }
41    }
42}

In the above three solutions, we first check if there are enough connections. If not, we return -1. Then, we build a graph based on the connections array and use depth-first search to count the number of connected components in the graph. Finally, we return numOfConnected - 1 as the result. These solutions are efficient with a time complexity of O(n + m) where m represents the number of connections.