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
Difficulty
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
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 2307: Check for Contradictions in Equations
Solved On The Same Day
- problem 1465: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
- problem 1477: Find Two Non-overlapping Sub-arrays Each With Target Sum
- problem 1482: Minimum Number of Days to Make m Bouquets
- problem 1488: Avoid Flood in The City
- problem 1524: Number of Sub-arrays With Odd Sum
- problem 1546: Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
- problem 1562: Find Latest Group of Size M
- problem 1567: Maximum Length of Subarray With Positive Product
- problem 1320: Minimum Distance to Type a Word Using Two Fingers
- problem 1697: Checking Existence of Edge Length Limited Paths
Extra
- 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