Problem 1319

Abstract / Summary

Given a network of computers, find how many operations are needed to connect all computers so they form one connected network.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1319.py

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        # union-find, copied from problem 721, simplified
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x]) # path compression
            return parent[x]

        def union(x, y):
            parent[find(x)] = find(y)

        parent = list(range(n))

        spare = 0 # redundant cables
        for a, b in connections:
            # already connected, can steal that cable
            if find(a) == find(b):
                spare += 1
            else:
                union(a, b)

        # number of disconnected networks
        disjunct = len(set([ find(i) for i in range(n) ]))
        # need one less cable to reconnect all of them
        need = disjunct - 1
        if spare >= need:
            return need
        else:
            return -1
29 lines | 922 bytes | submitted May 3, 2024 | GitHub   28% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 64% (400k+ submissions).

Typical patterns to solve this problem:
  • Breadth First Search
  • Depth First Search
  • Graph
  • Union Find
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The makeConnected method determines the minimum number of operations required to connect all n computers using the given list of existing cables (connections). It treats each computer as a node in an undirected graph and uses a union-find (disjoint set) structure to track connectivity. Redundant cables are counted as “spare” resources that can be repurposed to bridge separate components. If the number of spare cables is sufficient to connect all components, the method returns the required number of operations; otherwise it returns -1.

Key Steps

Initialization of the Disjoint Set

The algorithm begins by creating a parent list where each node is initially its own representative.

parent = list(range(n))

This establishes n singleton sets, one for each computer.

Find with Path Compression

A recursive find function locates the root of a node’s set. When a node’s parent is not itself, the function recursively finds the ultimate root and compresses the path by assigning the node directly to that root.

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # path compression
    return parent[x]

Path compression ensures that subsequent find calls on the same node become constant-time operations.

Union Operation

The union function merges two distinct sets by linking the root of one to the root of the other.

def union(x, y):
    parent[find(x)] = find(y)

Because the algorithm only needs to know whether two nodes are already connected, a simple assignment suffices without additional balancing heuristics.

Counting Redundant Cables

The main loop iterates over each cable in connections. For each pair (a, b), the algorithm checks whether the two endpoints already share a root. If they do, the cable is redundant and contributes to the spare counter; otherwise the two components are merged.

spare = 0
for a, b in connections:
    if find(a) == find(b):
        spare += 1
    else:
        union(a, b)

This step simultaneously builds the connectivity structure and tallies cables that can be repurposed.

Determining the Number of Components

After processing all cables, the algorithm computes the number of distinct roots, which corresponds to the count of disconnected networks.

disjunct = len(set([find(i) for i in range(n)]))

Each unique root represents an isolated component that must be linked to the others.

Final Decision Logic

The required number of new connections equals one less than the number of components (need = disjunct - 1). The algorithm compares this requirement with the available spare cables. If enough spares exist, it returns the exact number of operations; otherwise it signals impossibility with -1.

need = disjunct - 1
if spare >= need:
    return need
else:
    return -1

Edge Cases Handled

When n equals 0 or 1, the set of computers is trivially connected. The loop over connections executes zero times, spare remains 0, and the set comprehension yields a single root (or none), resulting in need being 0. The method correctly returns 0 because no operations are required.

If connections is empty but n is greater than 1, the loop does not add any unions, leaving each node as its own component. The disjunct count becomes n, and need becomes n-1. Since spare stays 0, the method returns -1, indicating that there are insufficient cables to form a network.

When all provided cables are redundant (for example, a fully connected subgraph within a larger set of isolated nodes), each redundant cable increments spare. The algorithm still correctly identifies the number of distinct components and uses the accumulated spare count to decide feasibility.

If the number of redundant cables exactly matches the number of required connections, the condition spare >= need holds, and the method returns the precise number of operations needed to achieve full connectivity.

Performance Optimizations

The implementation leverages path compression inside the find function, which flattens the tree structure of each set during lookups. This dramatically reduces the cost of subsequent find calls, especially in scenarios with many union operations.

The union step directly reassigns the parent of one root to another without additional rank tracking, which keeps the code lightweight while still benefiting from the compressed paths.

Computing the distinct component count uses a set comprehension that calls find for each node exactly once after all unions are performed. Because the paths are already compressed, this final pass incurs minimal overhead.

The spare cable counter eliminates the need for a separate pass to identify redundant edges, integrating that logic into the primary iteration over connections. This single-pass approach reduces overall work and memory usage.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a bunch of computers spread all over a room. You want every single computer to be able to talk to every other computer, but right now, some are disconnected from each other. Each computer is like a little island, and the cables are bridges between them.

The code starts by looking at every cable you have. If two computers are already connected through some other path, that extra cable is just sitting there doing nothing special, so it gets put into a pile called spare. If two computers are not connected yet, the code uses a cable to link them together. This way, many computers join into smaller groups.

After checking all the cables, it looks at how many separate groups of computers still cannot talk to each other. If there are four groups, you need at least three more cables to join them all into one big family. The code counts how many groups exist and figures out how many cables are needed to bridge the gaps. If the pile of spare cables is big enough to cover the number of cables needed to connect those groups, it tells you exactly how many cables you must move to make everything work perfectly. If you do not have enough spare cables, it means it is impossible to connect everyone.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 7.77 | σ = 1.05

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java
leetcode.ca C++ Java Python Go TS
Progiez C++ Java Python
github black-shadows C++
charles-wangkai Java
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JS
lkwq007 Python
shreymehul C#
suxrobGM C#
varunu28 Java
vthwang Java
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Java
leetcode.ca C++, Go, Java, Python, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JavaScript
lkwq007 Python
shreymehul C#
suxrobGM C#
varunu28 Java
vthwang Java
wisdompeak C++
26 links | 16 authors | 7 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

11 solutions   May 3, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality