1319. Number of Operations to Make Network Connected

Problem Description

Given n computers and a list of connections connections where connections[i] = [a<sub>i</sub>, b<sub>i</sub>] represents a connection between computers a<sub>i</sub> and b<sub>i</sub>, determine the minimum number of operations needed to make all computers connected. An operation involves removing a cable between two directly connected computers and placing it between any pair of disconnected computers. If it's impossible to connect all computers, return -1.

Solution: Union-Find

This problem can be efficiently solved using the Union-Find data structure. Union-Find excels at tracking connected components in a graph.

Algorithm:

1. Initialization: Create a Union-Find data structure with n nodes (computers). Each computer initially represents its own connected component.

2. Iterate through Connections: Process each connection [a, b] in the connections list.

   • Find: Use the find operation of the Union-Find to determine the root (representative) of the connected components containing computers a and b.
   • Union (if necessary): If the roots of a and b are different, it means they are in different connected components. Perform a union operation to merge these components. The number of connected components decreases by 1.
   • Redundant Connection: If the roots of a and b are the same, it means there's a redundant connection between already connected computers. Increment a counter redundant_connections.

3. Check Feasibility: After processing all connections, calculate the number of connected components remaining. If the number of connected components minus 1 is greater than the number of redundant_connections, it's impossible to connect all computers because we lack enough extra cables. Return -1 in this case.

4. Return Minimum Operations: Otherwise, the minimum number of operations needed is equal to the number of connected components minus 1.

Time Complexity: O(mα(n)), where m is the number of connections and α(n) is the inverse Ackermann function (practically constant for all realistic input sizes). The Union-Find operations (find and union) have an amortized time complexity of nearly O(1) due to path compression and union by rank optimizations.

Space Complexity: O(n), primarily for the Union-Find data structure (parent array).

Code Implementation (Python)

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        parent = list(range(n))
 
        def find(i):
            if parent[i] == i:
                return i
            parent[i] = find(parent[i])
            return parent[i]
 
        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            if root_i != root_j:
                parent[root_i] = root_j
                return True
            return False
 
        redundant_connections = 0
        num_connected_components = n
        for u, v in connections:
            if not union(u, v):
                redundant_connections += 1
            else:
                num_connected_components -= 1
 
        if num_connected_components - 1 > redundant_connections:
            return -1
        else:
            return num_connected_components - 1
 

Code Implementation (Java):

class Solution {
    private int[] parent;
 
    private int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        parent[i] = find(parent[i]);
        return parent[i];
    }
 
    private boolean union(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            return true;
        }
        return false;
    }
 
    public int makeConnected(int n, int[][] connections) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
 
        int redundantConnections = 0;
        int numConnectedComponents = n;
        for (int[] connection : connections) {
            if (!union(connection[0], connection[1])) {
                redundantConnections++;
            } else {
                numConnectedComponents--;
            }
        }
 
        if (numConnectedComponents - 1 > redundantConnections) {
            return -1;
        } else {
            return numConnectedComponents - 1;
        }
    }
}

The other languages (C++, Go, TypeScript) would follow a similar structure, leveraging their respective Union-Find implementations. The core logic remains the same.