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.
-1if 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 (). We need a mathematical property based on graph theory:
- Connectivity Requirement: To connect
nnodes into a single component (a tree structure), you strictly need at leastn - 1edges. 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”. - Component Counting: If there are enough total cables (), the problem reduces to counting how many separate connected components (islands) exist in our current graph using Union-Find or DFS/BFS.
- Operations Logic: To merge
kdisjoint components into a single network, we need exactlyk - 1additional edges connecting them together. Since we have verified that total cables , 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:
- Edge Count Check: First, verify if
len(connections) < n - 1. If true, return-1immediately as the network is impossible to connect regardless of topology. - Initialize DSU: Create a parent array where each node initially points to itself (
parent[i] = i). This representsnseparate components. - 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. - Calculate Result: After processing all edges, let
componentsbe the remaining count of disjoint sets. The minimum operations needed is(number of disjoint sets) - 1.
Complexity Analysis
- Time Complexity: , where is the number of connections and is the Inverse Ackermann function (effectively constant, usually ). 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 ().
- Space Complexity: 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 - 1handles 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_countto 1. The logic holds: result is1 - 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_countstarts at 1. Returns1 - 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).