Code Implementation

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1

        parent = [i for i in range(n)]

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py

        for u, v in connections:
            union(u, v)

        components = len(set(find(i) for i in range(n)))
        return components - 1
      

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        vector<int> parent(n);
        for (int i = 0; i < n; ++i) parent[i] = i;

        function<int(int)> find = [&](int x) {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        };

        for (auto& conn : connections) {
            int u = find(conn[0]), v = find(conn[1]);
            if (u != v) parent[u] = v;
        }

        int components = 0;
        for (int i = 0; i < n; ++i)
            if (find(i) == i) components++;
        return components - 1;
    }
};
      

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        int[] parent = new int[n];
        for (int i = 0; i < n; ++i) parent[i] = i;

        int find(int x) {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }

        for (int[] conn : connections) {
            int u = find(conn[0]), v = find(conn[1]);
            if (u != v) parent[u] = v;
        }

        int components = 0;
        for (int i = 0; i < n; ++i)
            if (find(i) == i) components++;
        return components - 1;
    }
}
      

var makeConnected = function(n, connections) {
    if (connections.length < n - 1) return -1;
    let parent = Array.from({length: n}, (_, i) => i);

    function find(x) {
        if (parent[x] !== x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    for (let [u, v] of connections) {
        let pu = find(u), pv = find(v);
        if (pu !== pv) parent[pu] = pv;
    }

    let components = 0;
    for (let i = 0; i < n; ++i)
        if (find(i) === i) components++;
    return components - 1;
};
      

Problem Description

You are given n computers, labeled from 0 to n - 1, and a list of existing direct network connections between pairs of computers, given as connections, where each connection is a pair [a, b] meaning computer a is directly connected to computer b.

Your task is to determine the minimum number of operations required to connect all computers into a single network, where an operation consists of removing an existing connection and connecting a pair of disconnected computers. You cannot create new cables; you can only re-use existing ones. If it is impossible to connect all computers, return -1.

Key constraints:

• Each connection can only be used once in an operation.
• There is exactly one valid solution, or it is impossible.
• Do not reuse or duplicate connections.

Thought Process

At first glance, it may seem that you need to connect all computers by adding or rearranging cables. A brute-force approach would try to connect every pair, but that's inefficient and doesn't respect the constraint of only reusing existing cables.

The key insight is that connecting n computers into a single network requires at least n - 1 cables (edges), forming a spanning tree. If there are fewer than n - 1 connections, it's impossible to connect everyone.

Next, we need to determine how many disconnected groups (connected components) there are. Each group needs to be connected to the rest, and connecting two groups requires one operation. So, the answer is the number of disconnected groups minus one, provided we have enough cables.

A fast way to track groups is with a Union-Find (Disjoint Set Union) data structure, which efficiently merges groups and finds their leaders.

Solution Approach

• Step 1: Check for Enough Cables
  To connect n computers, you need at least n - 1 cables. If connections.length < n - 1, return -1 immediately.
• Step 2: Initialize Union-Find
  Create a parent array where parent[i] is initially i for all computers. This helps to efficiently track connected components.
• Step 3: Union Operations
  For each connection [a, b], perform a union operation to merge their groups. Use path compression in the find operation for efficiency.
• Step 4: Count Connected Components
  After processing all connections, count how many unique root parents there are. Each unique root represents a disconnected group.
• Step 5: Calculate Result
  To connect all groups, you need components - 1 operations, where components is the number of disconnected groups.
• Why Union-Find?
  Union-Find is ideal here because it allows efficient merging and finding of groups, which is much faster than repeatedly scanning the entire network.

Example Walkthrough

Suppose n = 6 and connections = [[0,1],[0,2],[0,3],[1,2],[1,3]].

• Step 1: There are 5 connections, but we need at least 5 (n-1), so it's possible.
• Step 2: Each computer starts as its own group: [0,1,2,3,4,5].
• Step 3: Process connections:
  • Union(0,1): 0 and 1 are now in one group.
  • Union(0,2): 2 joins the group with 0 and 1.
  • Union(0,3): 3 joins the same group.
  • Union(1,2) and Union(1,3): already connected, so no change.
• Step 4: Computers 4 and 5 remain disconnected. So, we have 3 groups: {0,1,2,3}, {4}, {5}.
• Step 5: To connect all, we need 2 operations (3 groups - 1).

So, the answer is 2.

Time and Space Complexity

• Brute-force Approach: Would require checking all pairs and is at least O(n^2), which is too slow for large n.
• Optimized (Union-Find) Approach:
  • Time Complexity: O(n + m * α(n)), where n is the number of computers, m is the number of connections, and α is the inverse Ackermann function (nearly constant for practical n).
  • Space Complexity: O(n) for the parent array.

Summary

To solve the problem, we leverage the insight that connecting n nodes requires at least n-1 cables. We use Union-Find to efficiently track connected components, and the number of necessary operations is the number of disconnected groups minus one. This approach is both efficient and elegant, making use of well-known data structures to solve a network connectivity problem.