Skip to main content
Talentd

Number of Operations to Make Network Connected - Solution & Explanation

MediumDepth-First SearchBreadth-First SearchUnion FindGraph20 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

Problem Statement

There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. 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 between two directly connected computers, and place them between any pair of disconnected computers to make them directly 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.

 

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

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: There are not enough cables.

 

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 two computers are connected by more than one cable.

Approach Overview

Problem Overview: You are given n computers and a list of cable connections between them. Each cable connects two computers. The goal is to determine the minimum number of operations needed to connect the entire network so every computer can reach every other computer. If there are not enough cables to achieve this, return -1.

The key observation: a connected network of n nodes needs at least n-1 edges. If the number of cables is less than that, building a fully connected network is impossible regardless of rearrangement.

Approach 1: Union-Find to Determine Connected Components (Time: O(n + m * α(n)), Space: O(n))

This approach models the computers as nodes in a graph. Use the Union-Find (Disjoint Set Union) data structure to merge computers that are already connected by cables. Iterate through each connection and perform union(a, b). If both computers already share the same root, that cable is redundant and can be reused elsewhere. After processing all edges, count the number of unique connected components. To connect k components, you need k - 1 cables. If the number of redundant cables is at least k - 1, the network can be connected with that many operations; otherwise return -1. Path compression and union by rank keep operations nearly constant time.

Approach 2: Depth-First Search (DFS) Approach (Time: O(n + m), Space: O(n + m))

This approach explicitly explores the network using graph traversal. First build an adjacency list from the connections. Then iterate through all computers and run Depth-First Search from each unvisited node to mark its entire component. Each DFS traversal identifies one connected component. After counting components, compute the number of operations required as components - 1. Before doing this, check whether the total number of cables is at least n - 1; otherwise return -1. DFS works well because the problem reduces to counting how many isolated groups exist in the graph.

Recommended for interviews: The Union-Find approach is typically preferred. It directly tracks connectivity while efficiently detecting redundant edges. Interviewers often expect candidates to recognize that the task is essentially counting connected components in a graph and that extra edges can be repurposed. Implementing DFS demonstrates solid graph fundamentals, but Union-Find shows stronger familiarity with connectivity problems commonly seen in distributed systems and network modeling.

Approach 1: Union-Find to Determine Connected Components

This approach uses the Union-Find (or Disjoint Set Union, DSU) data structure. It helps in efficiently finding the number of connected components in the network. Initially, every computer is its own component. We then iterate over each connection and unite the components of the two connected computers. Finally, we count how many separate components remain, since that will determine the number of cables needed to connect them.

This C code employs the Union-Find data structure. We first initialize every computer such that each is its own parent (leader of its own set). We process every connection to unite connected computers. Finally, we calculate the number of connected components by checking which computers are their own parents, and subtract one from this number to find the minimum number of required operations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + c), where n is the number of computers and c is the number of connections. Essentially, this is equivalent to O(c) given c > n. Space Complexity: O(n) for storing parent and rank arrays.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS) Approach

In this approach, we consider the computers and connections as a graph and use Depth-First Search (DFS) to determine the number of connected components. If there are at least n - 1 connections, it is possible to make the computers connected; otherwise, it isn't. Once the number of connected components is known, the number of operations required is the number of components minus one.

This C code defines a DFS approach to identify connected components in a graph. The graph is built using an adjacency list representation, and DFS traverses through unvisited nodes to explore connected nodes. The number of traversals gives the number of connected components, and we calculate required operations by subtracting one.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + c), where n is the number of computers and c is the connections. Space Complexity: O(n), managing the graph and visited structure.

Try this approach in the editor →

Approach 3: Union-Find

We can use a union-find data structure to maintain the connectivity between computers. Traverse all connections, and for each connection (a, b), if a and b are already connected, then this connection is redundant, and we increment the count of redundant connections. Otherwise, we connect a and b, and decrement the number of connected components.

Finally, if the number of connected components minus one is greater than the number of redundant connections, it means we cannot connect all computers, so we return -1. Otherwise, we return the number of connected components minus one.

The time complexity is O(m times log n), and the space complexity is O(n). Here, n and m are the number of computers and the number of connections, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Union-Find to Determine Connected Components

Time Complexity: O(n + c), where n is the number of computers and c is the number of connections. Essentially, this is equivalent to O(c) given c > n. Space Complexity: O(n) for storing parent and rank arrays.

Depth-First Search (DFS) Approach

Time Complexity: O(n + c), where n is the number of computers and c is the connections. Space Complexity: O(n), managing the graph and visited structure.

Union-Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Union-Find (Disjoint Set)O(n + m * α(n))O(n)Best general solution for connectivity problems and detecting redundant edges efficiently
Depth-First Search (DFS)O(n + m)O(n + m)Useful when explicitly traversing the graph or when practicing DFS-based component counting

Video Solution

G-49. Number of Operations to Make Network Connected - DSU • take U forward • 177,154 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Operations to Make Network Connected easy or hard?
The problem is classified as Medium difficulty on LeetCode. The challenge is recognizing that the network can only be connected if there are at least n - 1 cables and that the task reduces to counting connected components in a graph.
Number of Operations to Make Network Connected Python/Java solution
Python and Java implementations typically use Union-Find with path compression and union by rank. The algorithm processes each connection, merges components, counts the remaining groups, and returns components minus one if enough redundant cables exist.
How to solve Number of Operations to Make Network Connected in O(n + m)?
First check if the number of connections is at least n - 1. If not, return -1 because a connected graph needs at least that many edges. Then count connected components using either Union-Find or DFS traversal. If there are k components, the minimum operations needed to connect the network is k - 1.
What is the best approach for Number of Operations to Make Network Connected?
Union-Find (Disjoint Set Union) is the most efficient and interview-friendly approach. It quickly merges connected computers and detects redundant cables while processing edges. After building the sets, count the number of connected components and compute the required operations as components minus one. The approach runs in near linear time O(n + m * α(n)).
Is Number of Operations to Make Network Connected asked at Google/Amazon/Meta?
Graph connectivity and Union-Find problems frequently appear in interviews at companies like Google, Amazon, Meta, and Microsoft. Variations of this problem test understanding of connected components, redundant edges, and efficient graph processing.
What data structure is used in Number of Operations to Make Network Connected?
The most common data structure is Union-Find (Disjoint Set Union) to track connected components efficiently. Alternatively, the network can be represented as an adjacency list and explored using Depth-First Search or Breadth-First Search.
What is the time complexity of Number of Operations to Make Network Connected?
The optimal solution runs in O(n + m) time where n is the number of computers and m is the number of connections. Union-Find operations are effectively constant due to path compression and union by rank. DFS traversal also runs in O(n + m) because each node and edge is visited at most once.

Ready to solve this problem?

Practice Number of Operations to Make Network Connected with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Validate Binary Search Tree