Watch 10 video solutions for Number of Operations to Make Network Connected, a medium level problem involving Depth-First Search, Breadth-First Search, Union Find. This walkthrough by take U forward has 159,670 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= connections.length <= min(n * (n - 1) / 2, 105)connections[i].length == 20 <= ai, bi < nai != biProblem 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 | Time | Space | When 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 |