Number of Operations to Make Network Connected

You have n computers numbered from 0 to n-1 and a list of ethernet cables, each connecting two computers. In one operation, you can remove a cable between two directly connected computers and place it between any pair of disconnected computers. Return the minimum number of operations needed to make all computers connected. If it is impossible, return -1.

This is LeetCode 1319: Number of Operations to Make Network Connected, and it is a clean application of Union-Find for graph connectivity.

Why this problem matters

This problem combines two fundamental graph concepts: connected components and redundant edges. In many graph problems, you need to figure out how a network breaks into pieces and whether you have enough resources to stitch it back together. The same reasoning appears in network design, cluster analysis, and even social network problems where you want to check if everyone is reachable from everyone else.

It also reinforces how Union-Find works as a tool. You process edges one at a time, merging components. When an edge connects two nodes that are already in the same component, you know that edge is redundant. That single observation is the key to solving this problem.

The key insight

Think of the network as a graph. Each computer is a node and each cable is an edge. If the graph has k connected components, you need exactly k-1 cables to connect them all into one. Where do those cables come from? From redundant edges within existing components.

An edge is redundant if both its endpoints are already in the same connected component. Removing it does not disconnect anything. So if you find at least k-1 redundant edges, you can repurpose them to bridge the k components together. If you have fewer redundant edges than k-1, it is impossible.

As a quick sanity check: you need at least n-1 cables total to connect n computers. If the number of cables is less than n-1, return -1 immediately.

The solution

def make_connected(n: int, connections: list[list[int]]) -> int:
    if len(connections) < n - 1:
        return -1

    parent = list(range(n))
    rank = [0] * 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:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True

    components = n
    for a, b in connections:
        if union(a, b):
            components -= 1

    return components - 1

We start with n components (each node is its own component). For every cable, we try to union the two endpoints. If they were in different components, the union succeeds and we decrease the component count by 1. If they were already connected, the union returns False, meaning this cable is redundant. After processing all edges, the answer is simply components - 1, the number of bridges we need.

The early check len(connections) < n - 1 handles the impossible case. If we do not have enough total cables, no amount of rearranging will help.

Visual walkthrough

The walkthrough shows how Union-Find processes each edge. Three edges merge nodes into one component. Two edges are redundant because their endpoints are already connected. With 3 components and 2 redundant cables, we have exactly enough to reconnect everything.

Complexity analysis

Here e is the number of edges (cables) and alpha(n) is the inverse Ackermann function, which grows so slowly that it is effectively constant for all practical input sizes. Each find and union operation runs in amortized O(alpha(n)) time thanks to path compression and union by rank.

Time: We initialize the parent and rank arrays in O(n), then process each of the e edges with a union operation. Total: O(n + e * alpha(n)).

Space: The parent and rank arrays each take O(n). No other data structures are needed. Total: O(n).

The building blocks

1. Union-Find with path compression and union by rank

The core data structure. Each node starts as its own parent. find walks up the parent chain to the root, compressing the path along the way. union merges two components by attaching the shorter tree under the taller one.

parent = list(range(n))
rank = [0] * 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:
        return False
    if rank[px] < rank[py]:
        px, py = py, px
    parent[py] = px
    if rank[px] == rank[py]:
        rank[px] += 1
    return True

The find function uses path splitting (each node points to its grandparent) as a simple form of path compression. The union function returns True when a merge actually happens and False when the nodes are already in the same component.

2. Counting components and detecting redundant edges

Once Union-Find is in place, counting components is simple. Start with n components. Each successful union reduces the count by 1. A failed union (same root) means the edge is redundant. You do not even need to count redundant edges explicitly, because the early exit check len(connections) < n - 1 guarantees feasibility.

components = n
for a, b in connections:
    if union(a, b):
        components -= 1

return components - 1

After processing all edges, components - 1 is both the number of operations needed and the number of redundant cables required. If we passed the initial check, we are guaranteed to have enough.

Edge cases

• Fewer cables than n-1: impossible to connect n nodes with fewer than n-1 edges, regardless of arrangement. Return -1 immediately.
• Already fully connected: all nodes are in one component after processing. components - 1 = 0. No operations needed.
• n=1: a single computer is already connected. Return 0.
• Duplicate edges: if the same cable appears twice, the second one is always redundant. Union-Find handles this naturally since both endpoints will already share a root.
• Every node is isolated: no edges at all. You need n-1 cables but have 0. Return -1.

From understanding to recall

You have seen how Union-Find cleanly solves this problem: process edges, count components, check feasibility. The logic is compact. But reproducing it under pressure requires more than understanding.

The details that trip people up: initializing parent as list(range(n)), returning False from union when roots match, and remembering that the answer is components - 1 (not the redundant edge count directly). These are small things, but they matter when you are writing code on a whiteboard.

Spaced repetition makes these details automatic. You write the Union-Find template from scratch, then the component counting loop, then combine them. After a few rounds at increasing intervals, the pattern flows out without hesitation.

Related posts

• Number of Provinces - Connected components with Union-Find
• Redundant Connection - Finding extra edges in graphs
• Course Schedule - Graph connectivity patterns

CodeBricks breaks Number of Operations to Make Network Connected into its Union-Find and component-counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a connectivity problem shows up in your interview, you do not hesitate. You just write it.