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.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph, Union Find
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 400 <= connections.length <= 60There are no duplicate connections and no self-loops.
Hints for Number of Operations to Make Network Connected
Hint 1
Connecting
ncomputers needs at leastn - 1cables — fewer than that is impossible.Hint 2
With enough cables, every redundant one inside a component can be moved somewhere useful.
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
- Return -1 if
len(connections) < n - 1. - Union-find to count components.
- 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 - 1Java
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)