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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| 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 |
G-49. Number of Operations to Make Network Connected - DSU • take U forward • 159,670 views views
Watch 9 more video solutions →Practice Number of Operations to Make Network Connected with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor