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 != biThis 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Number of Connected Components in an Undirected Graph - Union Find - Leetcode 323 - Python • NeetCode • 205,472 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