1319. Number of Operations to Make Network Connected
Problem Description
In this LeetCode problem, we are given a network of n
computers, indexed from 0
to n-1
. The connections between these computers are represented as a list of pairs, where each pair [ai, bi]
indicates a direct ethernet cable connection between the computers ai
and bi
. Even though direct connections exist only between certain pairs, every computer can be reached from any other computer through a series of connections, forming a network.
Our task is to make all computers directly or indirectly connected with the least number of operations. An operation consists of disconnecting an ethernet cable between two directly connected computers and reconnecting it to a pair of disconnected computers.
We seek to find the minimum number of such operations needed to connect the entire network. If it is impossible to connect all computers due to an insufficient number of cables, the function should return -1
.
Flowchart Walkthrough
Let's analyze LeetCode 1319, "Number of Operations to Make Network Connected" using the Flowchart. I'll guide you through the decision-making process based on this problem's specifics:
Is it a graph?
- Yes: The problem explicitly describes a network of computers connected by cables, forming a graph where computers are nodes, and cables are edges.
Is it a tree?
- No: The graph can have cycles since extra cables could form loops.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem deals with an undirected graph; cables do not have a direction and form a plain network.
Is the problem related to shortest paths?
- No: The task is to find the minimum number of operations to connect all computers, not the shortest path between them.
Does the problem involve connectivity?
- Yes: The goal is to ensure that all computers are connected, forming one entire network (one connected component).
Is the graph weighted?
- No: The graph is unweighted; each cable/connection has the same import without any specific weight(characteristics).
Conclusion: Based on the flowchart, using a graph-based method focusing on connectivity for an unweighted graph, DFS is appropriate. DFS can efficiently explore each connected component to determine how many additional connections (operations) are needed to connect all components into a single network.
Intuition
The solution revolves around the concept of the Union-Find algorithm, a common data structure used for disjoint-set operations. The core idea is to establish a way to check quickly if two elements are in the same subset and to unify two subsets into one.
Here's an intuitive breakdown of the approach:
-
Initialization: We start by assuming each computer forms its own single-computer network. This is represented by an array where each index represents a computer and contains its "parent." Initially, all computers are their own parents, forming
n
independent sets. -
Counting Redundant Connections: As we iterate through the list of connections, we use the Union-Find with path compression to determine if two computers are already connected. If they are in the same subset, this connection is redundant. We count redundant connections because they represent extra cables that we can use to connect other more significant parts of the network.
-
Unifying Sets: For each non-redundant connection, we unify the sets that the two computers belong to. This action reduces the number of independent sets by one since we are connecting two previously separate networks.
-
Determine Minimum Operations: After all direct connections are processed, the number of independent sets remaining (
n
) minus one (sincen-1
connections are required to connectn
computers in a single network) gives us the number of operations needed to connect the entire network. -
Check for Possibility: If we have more independent networks than redundant connections (extra cables) remaining, it's impossible to connect all computers, and we return
-1
. -
Result: If it's possible to connect all computers, we return the number of operations needed (
n-1
), which corresponds to the number of extra connections required to connect all disjoint networks.
By using Union-Find, we efficiently manage the merging of networks and avoid unnecessary complexity, leading us to the optimal number of operations required to connect the entire network.
Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.
Solution Approach
The solution for connecting all computers with a minimum amount of operations applies the Union-Find algorithm, which includes methods to find the set to which an element belongs, and to unite two sets. Here's a step-by-step walkthrough of how the implementation works:
-
Creating a
find
function: This function is recursive and is used to find the root parent of a computer. If the computer is its own parent, we return its value; otherwise, we recursively find the parent, applying path compression along the way by settingp[x]
to the root parent. Path compression flattens the structure, reducing the time complexity of subsequentfind
operations.def find(x): if p[x] != x: p[x] = find(p[x]) return p[x]
-
Initializing the Parent List: A list
p
of rangen
is initialized, signifying that each computer is initially its own parent, formingn
separate sets.p = list(range(n))
-
Iterating Over Connections: For each connection
[a, b]
inconnections
, the algorithm checks whethera
andb
belong to the same set by comparing the root parent found byfind(a)
andfind(b)
.for a, b in connections: if find(a) == find(b): cnt += 1 else: p[find(a)] = find(b) n -= 1
- If they are in the same set, this connection is redundant (extra), and a counter
cnt
is incremented. - If they are not, we unite the sets by making the root parent of
a
the parent of the root parent ofb
, effectively merging the two sets. We also decrement the count of separate networks (n
) by 1.
- If they are in the same set, this connection is redundant (extra), and a counter
-
Calculating Minimum Operations: Once all pairs are processed, the algorithm checks if there are enough spare (redundant) connections to connect the remaining separate networks. This is done by comparing
n - 1
(the minimum number of extra connections required) withcnt
(the number of spare connections). Ifn - 1
is greater thancnt
, it's impossible to connect all networks, and the function returns-1
. Otherwise, it returnsn - 1
as the number of operations required.return -1 if n - 1 > cnt else n - 1
The underlying logic of Union-Find with path compression ensures that the time complexity of the find
operation is almost constant (amortized O(alpha(n))
), where alpha
is the inverse Ackermann function, which grows extremely slowly and is less than 5 for all practical values of n
. This property makes our solution highly efficient for the given problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have a network with n = 4
computers and the following list of ethernet cable connections (connections
): [[0, 1], [1, 2], [1, 3], [2, 3]]
. We want to find the minimum number of operations to connect the network.
-
Creating the Parent List: We initialize a list
p = [0, 1, 2, 3]
, which signifies that each computer is initially its own parent. -
Iterating Over Connections: We process each pair in
connections
and track redundant connections with a countercnt = 0
.-
For
[0, 1]
,find(0)
returns0
andfind(1)
returns1
. Since they have different parents, we connect them by settingp[0]
as the parent ofp[1]
(or vice versa). Nowp = [0, 0, 2, 3]
, andn = 4 - 1 = 3
. -
For
[1, 2]
,find(1)
returns0
andfind(2)
returns2
. They are not in the same set, so we connect them, updatingp[2]
to0
andn
becomes2
. Nowp = [0, 0, 0, 3]
. -
For
[1, 3]
,find(1)
gives0
andfind(3)
gives3
. They belong to different sets, so we merge them, settingp[3]
to0
andn
becomes1
. Nowp = [0, 0, 0, 0]
. -
Finally, for
[2, 3]
,find(2)
andfind(3)
both return0
, indicating they are in the same set. This means the connection is redundant, we incrementcnt
to1
.
-
-
Calculating Minimum Operations: We have
n - 1 = 1 - 1 = 0
minimum extra connections required to connect all computers andcnt = 1
redundant connections.Since we already have one redundant connection and we need zero connections to unify the network (all computers have been connected through previous steps), we can perform
0
operations to connect the network.
Therefore, our function would return 0
for this example.
The example illustrates that by using Union-Find, we were able to merge disjoint sets efficiently, track redundant connections, and detect that no further operations were needed to fully connect the network.
Solution Implementation
1from typing import List
2
3class Solution:
4 def makeConnected(self, num_computers: int, connections: List[List[int]]) -> int:
5 # Helper function to find the root of a given computer using path compression
6 def find_root(computer):
7 if parent[computer] != computer:
8 parent[computer] = find_root(parent[computer])
9 return parent[computer]
10
11 # Initialization of a counter for spare cables (redundant connections)
12 spare_cables = 0
13
14 # Initialize the parent array where each computer is its own parent initially
15 parent = list(range(num_computers))
16
17 # Loop through each connection to unite the sets of computers
18 for comp_a, comp_b in connections:
19 root_a = find_root(comp_a)
20 root_b = find_root(comp_b)
21
22 # If the computers have the same root, we have found a redundant connection
23 if root_a == root_b:
24 spare_cables += 1
25 else:
26 # Union operation, setting the parent of one root to be the other
27 parent[root_a] = root_b
28 # Decrease the number of separate networks
29 num_computers -= 1
30
31 # If the number of available spare cables (redundant connections)
32 # is at least the number of operations needed to connect all computers
33 # we return the number of operations required (num_computers - 1)
34 # Otherwise, we do not have enough cables and return -1
35 return -1 if num_computers - 1 > spare_cables else num_computers - 1
36
37# Example usage:
38# sol = Solution()
39# result = sol.makeConnected(4, [[0,1],[0,2],[1,2]])
40# print(result) # Output should be 1
41
1class Solution {
2 // `parent` array where `parent[i]` represents the leader or parent of the ith node.
3 private int[] parent;
4
5 // Method to connect all computers using the minimum number of extra wires, if possible.
6 public int makeConnected(int n, int[][] connections) {
7 // Initialize the parent array to indicate each node is a leader of itself at the start.
8 parent = new int[n];
9 for (int i = 0; i < n; ++i) {
10 parent[i] = i;
11 }
12
13 // `redundantConnections` counts the number of redundant connections.
14 int redundantConnections = 0;
15
16 // Loop through the given connections to unite the computers.
17 for (int[] connection : connections) {
18 int computer1 = connection[0];
19 int computer2 = connection[1];
20
21 // If two computers have the same leader, the connection is redundant.
22 if (find(computer1) == find(computer2)) {
23 ++redundantConnections;
24 } else {
25 // Union operation: join two sets; set leader of `computer1`'s set to `computer2`'s leader.
26 parent[find(computer1)] = find(computer2);
27 // Decrease the number of sets (or components) as two sets have been merged into one.
28 --n;
29 }
30 }
31
32 // To connect all computers, we need at least `n - 1` connections.
33 // If `n - 1` is greater than `redundantConnections`, we can't make all computers connected.
34 // Otherwise, return `n - 1` connections needed to make all computers connected.
35 return n - 1 > redundantConnections ? -1 : n - 1;
36 }
37
38 // Method to recursively find the leader of the given node `x`.
39 private int find(int x) {
40 // Path compression: direct attachment of `x` to its leader to flatten the tree.
41 if (parent[x] != x) {
42 parent[x] = find(parent[x]);
43 }
44 return parent[x];
45 }
46}
47
1class Solution {
2public:
3 vector<int> parent; // Array to represent the parent of each node, initializing DSU structure.
4
5 // The function to calculate the minimum number of connections to make all computers connected.
6 int makeConnected(int n, vector<vector<int>>& connections) {
7 parent.resize(n); // Assign the size of the parent vector based on the number of computers.
8 for (int i = 0; i < n; ++i) parent[i] = i; // Initially, set each computer's parent to itself.
9 int extraConnections = 0; // A counter to keep track of extra connections (redundant edges).
10
11 // Loop through the list of connections
12 for (auto& edge : connections) {
13 int compA = edge[0], compB = edge[1]; // Computers A and B are connected.
14 if (find(compA) == find(compB)) {
15 // If they already have the same root, the connection is extra.
16 ++extraConnections;
17 } else {
18 // Union operation: connect these two components
19 parent[find(compA)] = find(compB);
20 --n; // Decrement the count of disconnected components.
21 }
22 }
23 // The minimum number of connections required is (number of components - 1).
24 // If we don't have enough extra connections to connect all components, return -1.
25 return n - 1 > extraConnections ? -1 : n - 1;
26 }
27
28 // The function to find the root of the component to which 'x' belongs.
29 int find(int x) {
30 if (parent[x] != x) {
31 parent[x] = find(parent[x]); // Path compression: make all nodes in the path point to the root.
32 }
33 return parent[x];
34 }
35};
36
1const parent: number[] = []; // Array to represent the parent of each node in the DSU structure.
2
3// The function to find the representative of the set that 'x' belongs to.
4function find(x: number): number {
5 if (parent[x] !== x) {
6 parent[x] = find(parent[x]); // Path compression: make all nodes in the path point to the root.
7 }
8 return parent[x];
9}
10
11// The function to calculate the minimum number of connections to make all computers connected.
12function makeConnected(n: number, connections: number[][]): number {
13 for (let i = 0; i < n; ++i) parent[i] = i; // Initially, set each computer's parent to itself.
14 let extraConnections = 0; // A counter to keep track of extra (redundant) connections.
15
16 // Loop through the list of connections.
17 for (const edge of connections) {
18 const compA = edge[0], compB = edge[1]; // Computers A and B are connected.
19 if (find(compA) === find(compB)) {
20 // If they already have the same root, the connection is extra.
21 ++extraConnections;
22 } else {
23 // Union operation: connect these two components.
24 parent[find(compA)] = find(compB);
25 --n; // Decrement the count of disconnected components.
26 }
27 }
28 // The minimum number of connections required is (number of components - 1).
29 // If there are not enough extra connections to connect all components, return -1.
30 return (n - 1) > extraConnections ? -1 : n - 1;
31}
32
Time and Space Complexity
Time Complexity
The time complexity of the given code mainly depends on the number of connections and the union-find operations performed on them. In the best-case scenario, where all connections are already in their own set, the find
operation takes constant time, thus the time complexity would be O(C)
, where C
is the number of connections. However, in the average and worst case, where the find
function may traverse up to n
nodes (with path compression, it would be less), the time complexity of each find
operation can be approximated to O(log*n)
, which is the inverse Ackermann function, very slowly growing and often considered almost constant. Therefore, for C
connections, the average time complexity is O(C * log*n)
.
The final check for whether the number of extra connections is sufficient to connect all components has a constant time complexity of O(1)
.
So, the overall time complexity of the algorithm is O(C * log*n)
.
Space Complexity
The space complexity is determined by the space needed to store the parent array p
, which contains n
elements. Hence, the space complexity is O(n)
for the disjoint set data structure.
Additionally, no other auxiliary space that scales with the problem size is used, so the total space complexity remains O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Want a Structured Path to Master System Design Too? Donāt Miss This!