Number of Operations to Make Network Connected
Number of Operations to Make Network Connected is a medium graphs problem solved with the connected components pattern.
The best approach, optimal (union-find), runs in O(n + m · α(n)) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dfs component count) up.
Problem
A data centre has n machines numbered 0 to n - 1. You are given connections, where connections[i] = [a, b] means a network cable directly links machines a and b. Two machines can talk if there is a path of cables between them.
In one operation you may unplug any existing cable and plug it back in between any two machines that are currently not linked by a cable. Return the minimum number of operations needed so that every machine can reach every other machine, or -1 if that is impossible.
Examples
Example 1
- Input
n = 5, connections = [[0,1],[1,2],[2,0],[3,4]]- Output
1- Why
- The cable 2-0 is redundant inside the triangle 0-1-2; move it to join 0 with 3.
Example 2
- Input
n = 6, connections = [[0,1],[0,2],[1,2],[3,4]]- Output
-1- Why
- Six machines need at least five cables, but only four exist.
Example 3
- Input
n = 4, connections = [[0,1],[1,2],[2,3]]- Output
0- Why
- The machines already form one chain, so nothing has to move.
Constraints
1 <= n <= 10^51 <= connections.length <= min(n * (n - 1) / 2, 10^5)connections[i] = [a, b]with0 <= a, b < nanda != b.- No pair of machines is joined by more than one cable.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (DFS component count) | O(n + m) | O(n + m) |
| Optimal (union-find) | O(n + m · α(n)) | O(n) |
1Brute force (DFS component count)
O(n + m)Every machine and every cable is visited a constant number of times (m = number of cables).O(n + m)The adjacency list stores each cable twice; the stack and visited array are O(n).Build an adjacency list, count connected components with an iterative DFS, and answer components - 1 (or -1 if there are fewer than n - 1 cables).
- If
connections.length < n - 1, return -1. - Build the adjacency list from the cables.
- For every unvisited machine, start a DFS that marks its whole component and add one to the count.
- Return
count - 1.
class Solution {
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] c : connections) {
adj.get(c[0]).add(c[1]);
adj.get(c[1]).add(c[0]);
}
boolean[] seen = new boolean[n];
int components = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int s = 0; s < n; s++) {
if (seen[s]) continue;
components++;
seen[s] = true;
stack.push(s);
while (!stack.isEmpty()) {
int u = stack.pop();
for (int v : adj.get(u)) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
}
return components - 1;
}
}class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1:
return -1
adj = [[] for _ in range(n)]
for a, b in connections:
adj[a].append(b)
adj[b].append(a)
seen = [False] * n
components = 0
for s in range(n):
if seen[s]:
continue
components += 1
seen[s] = True
stack = [s]
while stack:
u = stack.pop()
for v in adj[u]:
if not seen[v]:
seen[v] = True
stack.append(v)
return components - 1class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if ((int)connections.size() < n - 1) return -1;
vector<vector<int>> adj(n);
for (auto& c : connections) {
adj[c[0]].push_back(c[1]);
adj[c[1]].push_back(c[0]);
}
vector<bool> seen(n, false);
int components = 0;
vector<int> stack;
for (int s = 0; s < n; s++) {
if (seen[s]) continue;
components++;
seen[s] = true;
stack.push_back(s);
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
for (int v : adj[u]) {
if (!seen[v]) {
seen[v] = true;
stack.push_back(v);
}
}
}
}
return components - 1;
}
};function makeConnected(n, connections) {
if (connections.length < n - 1) return -1;
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of connections) {
adj[a].push(b);
adj[b].push(a);
}
const seen = new Array(n).fill(false);
let components = 0;
const stack = [];
for (let s = 0; s < n; s++) {
if (seen[s]) continue;
components++;
seen[s] = true;
stack.push(s);
while (stack.length > 0) {
const u = stack.pop();
for (const v of adj[u]) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
}
return components - 1;
}2Optimal (union-find)
O(n + m · α(n))Each find is nearly constant with path compression and union by size.O(n)Only the parent and size arrays; no adjacency list is built.Start with n separate sets. Each cable that joins two different sets merges them and reduces the component count by one; cables inside one set are spare. With enough cables, the answer is components - 1.
- If
connections.length < n - 1, return -1. - Initialise
parent[i] = iandcomponents = n. - For each cable, find both roots (with path compression); if they differ, union them by size and decrement
components. - Return
components - 1.
class Solution {
private int[] parent, size;
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
int components = n;
for (int[] c : connections) {
int a = find(c[0]), b = find(c[1]);
if (a == b) continue;
if (size[a] < size[b]) { int t = a; a = b; b = t; }
parent[b] = a;
size[a] += size[b];
components--;
}
return components - 1;
}
}class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1:
return -1
parent = list(range(n))
size = [1] * n
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
components = n
for u, v in connections:
a, b = find(u), find(v)
if a == b:
continue
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
components -= 1
return components - 1class Solution {
vector<int> parent, sz;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if ((int)connections.size() < n - 1) return -1;
parent.assign(n, 0);
sz.assign(n, 1);
for (int i = 0; i < n; i++) parent[i] = i;
int components = n;
for (auto& c : connections) {
int a = find(c[0]), b = find(c[1]);
if (a == b) continue;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
components--;
}
return components - 1;
}
};function makeConnected(n, connections) {
if (connections.length < n - 1) return -1;
const parent = Array.from({ length: n }, (_, i) => i);
const size = new Array(n).fill(1);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let components = n;
for (const [u, v] of connections) {
let a = find(u), b = find(v);
if (a === b) continue;
if (size[a] < size[b]) [a, b] = [b, a];
parent[b] = a;
size[a] += size[b];
components--;
}
return components - 1;
}Edge cases to test
- Fewer than
n - 1cables: impossible no matter how they are moved - A single machine: already connected, answer 0
- Machines that appear in no cable at all (isolated components)
- Many cables inside one component and many isolated machines
Hints
Hint 1
A connected network on n machines needs at least n - 1 cables. If there are fewer, the answer is -1.
Hint 2
If there are enough cables, every extra cable inside a component can be moved. Joining c components takes exactly c - 1 moves.
Hint 3
So the whole problem reduces to counting connected components: use DFS/BFS or a disjoint set union.
FAQ
What is the best time complexity for Number of Operations to Make Network Connected?
Optimal (union-find) runs in O(n + m · α(n)) time and O(n) extra space. Each find is nearly constant with path compression and union by size.
Which pattern does Number of Operations to Make Network Connected use?
It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.
Is there a brute force solution for Number of Operations to Make Network Connected?
Yes. Brute force (DFS component count) takes O(n + m) time and O(n + m) space. Build an adjacency list, count connected components with an iterative DFS, and answer components - 1 (or -1 if there are fewer than n - 1 cables).
Which edge cases should I test for Number of Operations to Make Network Connected?
Fewer than n - 1 cables: impossible no matter how they are moved; A single machine: already connected, answer 0; Machines that appear in no cable at all (isolated components); Many cables inside one component and many isolated machines.