Domain 2MediumMEDIUM

Number of Operations to Make Network Connected

Count connected components and check edge sufficiency to determine minimum moves.

Domain: medium•Updated: 2026-09-14
#Union-Find#Disjoint Set Union#O(E * alpha(N))#O(N)

Problem Breakdown

We are given a network of n computers (nodes) and existing ethernet cables (edges). The goal is to ensure the graph becomes fully connected. We can achieve this by removing redundant edges from currently connected components and using them to connect disconnected components.

Inputs:

  • n: Integer representing the number of nodes (0 to n-1).
  • connections: List of [u, v] pairs indicating existing undirected edges.

Outputs:

  • Minimum operations required to make the graph connected.
  • -1 if it is impossible regardless of how we move cables.

Intuition

A brute force approach would try moving every cable one by one and checking connectivity using BFS/DFS each time, which is inefficient (O(E⋅V)O(E \cdot V)). We need a mathematical property based on graph theory:

  1. Connectivity Requirement: To connect n nodes into a single component (a tree structure), you strictly need at least n - 1 edges. If the total number of available cables (len(connections)) is less than this threshold, it is physically impossible to form a connected graph because we lack sufficient “wires”.
  2. Component Counting: If there are enough total cables (E≥n−1E \ge n-1), the problem reduces to counting how many separate connected components (islands) exist in our current graph using Union-Find or DFS/BFS.
  3. Operations Logic: To merge k disjoint components into a single network, we need exactly k - 1 additional edges connecting them together. Since we have verified that total cables ≥n−1\ge n-1, there are guaranteed to be enough “spare” (redundant) cables within the existing connected components to perform these merges without needing external wires. Thus, the answer is simply (number of disjoint sets) - 1.

Approach

We will use a Union-Find (Disjoint Set Union) data structure because it efficiently tracks connected components and handles edge merging operations in nearly constant time per operation with path compression.

Algorithm Steps:

  1. Edge Count Check: First, verify if len(connections) < n - 1. If true, return -1 immediately as the network is impossible to connect regardless of topology.
  2. Initialize DSU: Create a parent array where each node initially points to itself (parent[i] = i). This represents n separate components.
  3. Process Connections: Iterate through every cable in connections. For each pair (u, v), find the root of both nodes using path compression. If they have different roots (different sets), union them and decrement a counter tracking the number of active disjoint components. Redundant edges connecting already connected nodes are ignored for component counting purposes but contribute to edge sufficiency check done in step 1.
  4. Calculate Result: After processing all edges, let components be the remaining count of disjoint sets. The minimum operations needed is (number of disjoint sets) - 1.

Complexity Analysis

  • Time Complexity: O(E⋅α(N))O(E \cdot \alpha(N)), where EE is the number of connections and α\alpha is the Inverse Ackermann function (effectively constant, usually ≤4\le 4). This simplifies to nearly linear time with respect to input size. Path compression ensures amortized efficiency even without union-by-rank heuristic in this implementation context for LeetCode constraints (N≤105N \le 10^5).
  • Space Complexity: O(N)O(N) for storing the parent array and recursion stack (or iterative variables) within Union-Find.

Solution

from typing import List

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        # If we have fewer cables than needed to form a tree (n-1 edges), 
        # it is impossible to connect all computers.
        if len(connections) < n - 1:
            return -1
        
        parent = list(range(n))
        
        def find(i):
            root = i
            while parent[root] != root:
                root = parent[root]
            
            # Path compression optimization to flatten the tree structure
            curr = i
            while curr != root:
                next_node = parent[curr]
                parent[curr] = root
                curr = next_node
            
            return root
        
        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            
            if root_i != root_j:
                # Merge the two sets by attaching one root to another
                parent[root_i] = root_j
                return True
            return False
            
        components_count = n
        
        for u, v in connections:
            if union(u, v):
                components_count -= 1
                
        # To connect 'components_count' disjoint islands into one network, 
        # we need exactly (components_count - 1) edges.
        return components_count - 1

Edge Cases Handled

  • Insufficient Cables: The check len(connections) < n - 1 handles cases where the graph cannot be connected regardless of topology, returning -1. This covers scenarios like Example 3.
  • Already Connected Graph: If all nodes are already in one component after processing edges (e.g., Example 4), unions will reduce components_count to 1. The logic holds: result is 1 - 1 = 0. Redundant cables within a single connected component do not decrement the count further because they connect existing roots, returning False from union().
  • Single Node (n=1): Loop over connections doesn’t run or runs empty if no edges. components_count starts at 1. Returns 1 - 1 = 0. Correct as a single node is already connected to itself.
  • Disconnected Graph: If graph has multiple components and enough edges exist to bridge them, the count reflects exactly how many bridges are needed (count - 1).