Log inSign up
mediumLeetCodeNot Started

Number of Operations to Make Network Connected

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

There are n computers numbered from 0 to n - 1 and a network of ethernet cables connecting them where connections[i] = [ai, bi] connects computer ai and bi together. Any computer can reach any other computer directly or indirectly through the network.

You are given an initial computer network connections. You can extract certain cables and place them between any pair of disconnected computers to make them connected.

Return the *minimum number of times you need to do this in order to make all the computers connected*. If it is not possible, return -1.

Constraints:

  • 1 <= n <= 105
  • 1 <= connections.length <= min(n * (n - 1) / 2, 105)
  • connections[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no repeated connections.
  • No computer is connected to itself.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the fundamental theorem of connected graphs: a connected graph on V vertices must possess at least V - 1 edges.
  • Identify redundant edges (cycles) in an undirected graph using DSU.
  • Count connected components using DFS/BFS vs. Disjoint Set Union (Union-Find).
  • Calculate the exact operations needed to merge multiple components.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a problem asks for rewiring/reconnecting edges to unify a network, first check the necessary edge count lower bound (E >= V - 1). If satisfied, the number of operations required to link disconnected components is always (number of components) - 1.

1. DFS Traversal with Component Counting

Intuition

First check if the total edge count is at least n - 1. If not, return -1. Next, build an adjacency list of the graph and run standard Depth-First Search from every unvisited computer. Each DFS invocation explores an entire connected component. Count the total number of components C; the answer is C - 1.

Algorithm

  1. If connections.length < n - 1, return -1.
  2. Build an undirected adjacency list adj of size n.
  3. Initialize visited array of size n filled with false.
  4. Initialize components = 0.
  5. For each vertex i from 0 to n - 1:
  6. If !visited[i]:
  7. Increment components.
  8. Perform recursive dfs(i) to mark all reachable computers as visited.
  9. Return components - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4void dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
5 visited[u] = true;
6 for (int v : adj[u]) {
7 if (!visited[v]) {
8 dfs(v, adj, visited);
9 }
10 }
11}
12
13int makeConnectedDFS(int n, std::vector<std::vector<int>>& connections) {
14 if (connections.size() < n - 1) return -1;
15
16 std::vector<std::vector<int>> adj(n);
17 for (const auto& conn : connections) {
18 adj[conn[0]].push_back(conn[1]);
19 adj[conn[1]].push_back(conn[0]);
20 }
21
22 std::vector<bool> visited(n, false);
23 int components = 0;
24
25 for (int i = 0; i < n; ++i) {
26 if (!visited[i]) {
27 components++;
28 dfs(i, adj, visited);
29 }
30 }
31
32 return components - 1;
33}
34
35int main() {
36 std::vector<std::vector<int>> connections = {{0,1},{0,2},{0,3},{1,2},{1,3}};
37 std::cout << "Operations (DFS): " << makeConnectedDFS(6, connections) << std::endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(V + E) where V is n and E is connections.length. Visiting each node and edge once during DFS.
  • Space complexity: O(V + E) to store the adjacency list and recursion stack.

2. BFS Traversal with Queue

Intuition

Instead of recursion which may cause call-stack overflow on large sparse graphs (N = 105), use an iterative Queue-based Breadth-First Search (BFS) to discover connected components.

Algorithm

  1. If connections.length < n - 1, return -1.
  2. Build adjacency list from connections.
  3. Initialize visited array of size n and queue.
  4. Initialize components = 0.
  5. For each node i from 0 to n - 1:
  6. If !visited[i]:
  7. components++
  8. Push i to queue and mark visited[i] = true.
  9. While queue is not empty:
  10. Pop u, iterate over neighbors v. If !visited[v], mark visited and push to queue.
  11. Return components - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5int makeConnectedBFS(int n, std::vector<std::vector<int>>& connections) {
6 if (connections.size() < n - 1) return -1;
7
8 std::vector<std::vector<int>> adj(n);
9 for (const auto& c : connections) {
10 adj[c[0]].push_back(c[1]);
11 adj[c[1]].push_back(c[0]);
12 }
13
14 std::vector<bool> visited(n, false);
15 int components = 0;
16
17 for (int i = 0; i < n; ++i) {
18 if (!visited[i]) {
19 components++;
20 std::queue<int> q;
21 q.push(i);
22 visited[i] = true;
23
24 while (!q.empty()) {
25 int u = q.front();
26 q.pop();
27 for (int v : adj[u]) {
28 if (!visited[v]) {
29 visited[v] = true;
30 q.push(v);
31 }
32 }
33 }
34 }
35 }
36
37 return components - 1;
38}
39
40int main() {
41 std::vector<std::vector<int>> connections = {{0,1},{0,2},{1,2}};
42 std::cout << "Operations (BFS): " << makeConnectedBFS(4, connections) << std::endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(V + E) where V is n and E is connections.length.
  • Space complexity: O(V + E) for adjacency list and BFS queue.

3. Disjoint Set Union (DSU) - In-Place Component Tracking

Intuition

Instead of allocating an adjacency list with 2E pointers, process the raw edge list directly using Disjoint Set Union (DSU). Start with n distinct components. For each cable (u, v), find their roots. If find(u) != find(v), unite them and decrement the component count by 1. If find(u) == find(v), this cable is a redundant cycle cable that can be freely relocated. After processing all edges, return components - 1.

Algorithm

  1. If connections.length < n - 1, return -1.
  2. Initialize parent array with parent[i] = i for i = 0 to n - 1.
  3. Set components = n.
  4. For each edge [u, v] in connections:
  5. rootU = find(u), rootV = find(v)
  6. If rootU != rootV:
  7. parent[rootU] = rootV
  8. components--
  9. Return components - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5class DSU {
6 std::vector<int> parent;
7 int components;
8public:
9 DSU(int n) : parent(n), components(n) {
10 std::iota(parent.begin(), parent.end(), 0);
11 }
12 int find(int i) {
13 if (parent[i] == i) return i;
14 return parent[i] = find(parent[i]);
15 }
16 bool unite(int i, int j) {
17 int rootI = find(i);
18 int rootJ = find(j);
19 if (rootI != rootJ) {
20 parent[rootI] = rootJ;
21 components--;
22 return true;
23 }
24 return false;
25 }
26 int getComponents() const {
27 return components;
28 }
29};
30
31int makeConnected(int n, std::vector<std::vector<int>>& connections) {
32 if (connections.size() < n - 1) return -1;
33
34 DSU dsu(n);
35 for (const auto& conn : connections) {
36 dsu.unite(conn[0], conn[1]);
37 }
38
39 return dsu.getComponents() - 1;
40}
41
42int main() {
43 std::vector<std::vector<int>> connections = {{0,1},{0,2},{0,3},{1,2},{1,3}};
44 std::cout << "Optimal Operations (DSU): " << makeConnected(6, connections) << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(E * alpha(V)) where E is connections.length and alpha is the inverse Ackermann function (nearly O(1)).
  • Space complexity: O(V) auxiliary space for DSU parent array, without allocating any adjacency list.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS Component CountingO(V + E)O(V + E)Intuitive recursive traversal.Requires allocating an explicit adjacency list and deep recursion stack.
2.BFS Component CountingO(V + E)O(V + E)Avoids call-stack overflow via explicit queue.Still requires adjacency list allocation.
3.Disjoint Set Union (DSU)OptimalO(E * alpha(V))O(V)Streamlined edge processing without adjacency list overhead; naturally tracks redundant cables.Requires implementing the Union-Find data structure.

Common Pitfalls & Crucial Edge Cases

Checking whether redundant cables >= C - 1 instead of simply checking connections.length >= n - 1.

The conditions are mathematically equivalent: total edges = tree edges + redundant edges. If total edges >= n - 1, redundant edges are guaranteed to be >= C - 1.

Forgetting to initialize parent array with identity values parent[i] = i.

Every node starts in its own individual component.

Crucial Edge Cases to Validate:

  • connections.length < n - 1 — Immediately return -1 without running traversal.
  • n = 1 — connections can be empty; components = 1, returns 1 - 1 = 0 operations.
  • All computers already in a single component (C = 1) — Returns C - 1 = 0 operations.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the lower-bound condition first: 'If cables < n - 1, return -1 immediately by tree properties.'
  2. Explain how DSU directly identifies cycle/redundant edges and decrements component counts in O(alpha(V)) time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the absolute minimum number of cables required to connect N computers?

2.If we have C connected components and connections.length >= n - 1, how many cable movements are needed?

3.What happens when find(u) == find(v) during DSU edge processing?

Back to DSA Sheet