1319. Number of Operations to Make Network Connected

MediumDepth-First SearchBreadth-First SearchUnion FindGraph
Leetcode Link

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.

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:

  1. 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.

  2. 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.

  3. 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.

  4. Determine Minimum Operations: After all direct connections are processed, the number of independent sets remaining (n) minus one (since n-1 connections are required to connect n computers in a single network) gives us the number of operations needed to connect the entire network.

  5. 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.

  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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:

  1. 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 setting p[x] to the root parent. Path compression flattens the structure, reducing the time complexity of subsequent find operations.

    1def find(x):
2    if p[x] != x:
3        p[x] = find(p[x])
4    return p[x]

  2. Initializing the Parent List: A list p of range n is initialized, signifying that each computer is initially its own parent, forming n separate sets.

    1p = list(range(n))

  3. Iterating Over Connections: For each connection [a, b] in connections, the algorithm checks whether a and b belong to the same set by comparing the root parent found by find(a) and find(b).

    1for a, b in connections:
2    if find(a) == find(b):
3        cnt += 1
4    else:
5        p[find(a)] = find(b)
6        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 of b, effectively merging the two sets. We also decrement the count of separate networks (n) by 1.

  4. 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) with cnt (the number of spare connections). If n - 1 is greater than cnt, it's impossible to connect all networks, and the function returns -1. Otherwise, it returns n - 1 as the number of operations required.

    1return -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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example 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.

  1. Creating the Parent List: We initialize a list p = [0, 1, 2, 3], which signifies that each computer is initially its own parent.

  2. Iterating Over Connections: We process each pair in connections and track redundant connections with a counter cnt = 0.

    • For [0, 1], find(0) returns 0 and find(1) returns 1. Since they have different parents, we connect them by setting p[0] as the parent of p[1] (or vice versa). Now p = [0, 0, 2, 3], and n = 4 - 1 = 3.

    • For [1, 2], find(1) returns 0 and find(2) returns 2. They are not in the same set, so we connect them, updating p[2] to 0 and n becomes 2. Now p = [0, 0, 0, 3].

    • For [1, 3], find(1) gives 0 and find(3) gives 3. They belong to different sets, so we merge them, setting p[3] to 0 and n becomes 1. Now p = [0, 0, 0, 0].

    • Finally, for [2, 3], find(2) and find(3) both return 0, indicating they are in the same set. This means the connection is redundant, we increment cnt to 1.

  3. Calculating Minimum Operations: We have n - 1 = 1 - 1 = 0 minimum extra connections required to connect all computers and cnt = 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

DFS Fundamentals

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

BFS Fundamentals

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

DSU/Union Find Fundamentals

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ