Union-Find (Disjoint Set) Implementation in Python

10 min readintermediateUpdated 2026-03-01

NexusBro EditorialDeveloper Tooling ResearchUpdated 2026-03-01

Key Takeaways

✓Python's readability makes it ideal for learning Union-Find (Disjoint Set).
✓The implementation achieves O(α(n)) average time complexity.
✓Python's built-in data structures complement Union-Find (Disjoint Set) implementations.
✓Type hints improve code clarity and catch bugs early.

Union-Find (Disjoint Set) in Python: Overview

Python is an excellent language for implementing Union-Find (Disjoint Set) thanks to its readable syntax and rich standard library. It maintains a collection of disjoint sets with near-constant time union and find operations. Path compression and union by rank achieve inverse Ackermann amortized time, effectively O(1). In this tutorial, we implement Union-Find (Disjoint Set) in Python using idiomatic patterns, type hints, and thorough documentation. Python's dynamic typing and list comprehensions allow for concise implementations, while type hints from the typing module provide additional safety. We also leverage Python's built-in testing capabilities to verify correctness. Whether you are a beginner learning algorithms or an experienced developer preparing for interviews, this Python implementation will serve as a clear reference.

Python Implementation

Below is a clean, idiomatic Python implementation of Union-Find (Disjoint Set). The code uses type hints for clarity and includes docstrings explaining each function's purpose. Note how Python's syntax makes the algorithm's logic transparent and easy to follow. Each function is designed to be self-contained and testable.

python

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # number of components

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        self.count -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

uf = UnionFind(10)
uf.union(0, 1); uf.union(1, 2); uf.union(3, 4)
print(uf.connected(0, 2))  # True
print(uf.connected(0, 3))  # False
print(uf.count)  # 7

Step-by-Step Explanation

Let us walk through how this Python implementation works: Step 1: Initialize each element as its own parent (self-loop) — In our Python code, this corresponds to the initial setup and input validation. Step 2: Find: follow parent pointers to root, compress path — In our Python code, this corresponds to the core loop body where the main logic executes. Step 3: Union: find roots of both elements, connect smaller tree to larger — In our Python code, this corresponds to the core loop body where the main logic executes. Step 4: Union by rank: track tree height, attach shorter to taller — In our Python code, this corresponds to the core loop body where the main logic executes. Step 5: Path compression: point all visited nodes directly to root — In our Python code, this corresponds to the final return statement and result construction. Python's list slicing and built-in functions simplify several of these steps compared to lower-level languages. The implementation prioritizes clarity over micro-optimization, making it ideal for learning and interview settings.

Did You Get the Big O Right? NexusBro Will Tell You in Seconds.

Paste your algorithm. Get complexity analysis, edge cases, and optimizations.

Test My Algorithm

Complexity Analysis

This Python implementation of Union-Find (Disjoint Set) has the following complexity profile: - Time: Best O(α(n)), Average O(α(n)), Worst O(α(n)) - Space: O(n) Python's overhead from dynamic typing and interpreted execution means constant factors are higher than compiled languages. However, for algorithm analysis, the asymptotic complexity remains the same. For performance-critical applications, consider using NumPy arrays or Cython extensions. Python's built-in sort uses TimSort, which achieves O(n log n) worst case and excels on partially sorted data. Understanding how Union-Find (Disjoint Set) compares to built-in methods helps you make informed decisions in production code.

Testing Your Implementation

Always test your Union-Find (Disjoint Set) implementation with a variety of inputs: 1. Empty input: Verify the function handles empty lists or None gracefully. 2. Single element: Ensure no errors occur with minimal input. 3. Already processed input: Check that the algorithm handles best-case scenarios correctly. 4. Reverse order: Test worst-case behavior. 5. Duplicates: Verify correct handling of repeated values. 6. Large inputs: Stress test with thousands of elements to confirm acceptable performance. Python's unittest and pytest frameworks make it easy to write comprehensive test suites. Use parameterized tests to cover many cases with minimal code duplication. Property-based testing with Hypothesis can also uncover edge cases you might not think of manually.

Python-Specific Optimizations

Python offers several ways to optimize your Union-Find (Disjoint Set) implementation: - Use collections.deque for O(1) append and pop operations from both ends. - Leverage itertools for memory-efficient iteration over large datasets. - Use functools.lru_cache for memoization in recursive implementations. - Consider array.array for type-homogeneous numeric data with lower memory overhead. - Profile with cProfile before optimizing to identify actual bottlenecks. Remember that premature optimization is the root of all evil. Start with a correct, readable implementation, measure performance, and optimize only where necessary. Python's ecosystem provides excellent profiling and benchmarking tools that make this process straightforward.

Unlock Unlimited QA Audits for $15.99/mo

Free: 5 audits/day. Pro $15.99/mo: 50/day + 250 pages. Pro Max $99/mo: unlimited audits, 10K pages, API access.

See Plans

Frequently Asked Questions

Is Python good for implementing Union-Find (Disjoint Set)?

Yes, Python is excellent for learning and implementing Union-Find (Disjoint Set). Its readable syntax makes the algorithm logic clear, and its standard library provides useful supporting data structures. While Python is slower than compiled languages, the asymptotic complexity is identical, making it perfect for understanding and interviews.

How does Python's built-in sort compare to Union-Find (Disjoint Set)?

Python's built-in sort uses TimSort, a hybrid merge-sort and insertion-sort algorithm with O(n log n) worst case. Depending on Union-Find (Disjoint Set)'s complexity class, it may be faster or slower for specific inputs. Built-in sort is highly optimized in C, so it will outperform pure Python implementations.

Should I use type hints in my Union-Find (Disjoint Set) Python code?

Yes, type hints improve code readability, enable better IDE support, and help catch type-related bugs early. They are especially valuable in algorithm implementations where the types of inputs and outputs should be clear to readers.

Can I use Union-Find (Disjoint Set) in Python for large datasets?

For large datasets, consider the algorithm's complexity. If Union-Find (Disjoint Set) has O(α(n)) worst case, it may be slow for very large inputs. Python's NumPy and Pandas libraries offer optimized C-based alternatives for data-heavy operations.

What Python version should I use for Union-Find (Disjoint Set)?

Use Python 3.10 or later for the best experience. Recent versions offer structural pattern matching, improved type hints, and performance improvements that benefit algorithm implementations.

Share this article

X LinkedIn Reddit WhatsApp

Union Find Complete Guide Union Find Typescript Union Find Java Kruskal Algorithm Complete Guide

Unlock Unlimited QA Audits for $15.99/mo

Free: 5 audits/day. Pro $15.99/mo: 50/day + 250 pages. Pro Max $99/mo: unlimited audits, 10K pages, API access.

See Plans

Noizz helps you discover and compare the best new products and tools. Try it free →

Is YOUR site's SEO this optimized?

Find out in 60 seconds with a free QA audit.

Free SEO Check

Is your site built to last?

Run a free QA audit and get your Site Health Score in seconds.

Check Your Site Free

No signup required

QA Score Checker·Compare Sites·Industry Benchmarks

Union-Find (Disjoint Set) in Python: Overview

Python Implementation

python

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # number of components

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        self.count -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

uf = UnionFind(10)
uf.union(0, 1); uf.union(1, 2); uf.union(3, 4)
print(uf.connected(0, 2))  # True
print(uf.connected(0, 3))  # False
print(uf.count)  # 7

Step-by-Step Explanation

Complexity Analysis

Testing Your Implementation

Python-Specific Optimizations

Frequently Asked Questions

Is Python good for implementing Union-Find (Disjoint Set)?

How does Python's built-in sort compare to Union-Find (Disjoint Set)?

Should I use type hints in my Union-Find (Disjoint Set) Python code?

Can I use Union-Find (Disjoint Set) in Python for large datasets?

What Python version should I use for Union-Find (Disjoint Set)?

Use Python 3.10 or later for the best experience. Recent versions offer structural pattern matching, improved type hints, and performance improvements that benefit algorithm implementations.

Key Takeaways

Union-Find (Disjoint Set) in Python: Overview

Python Implementation

Step-by-Step Explanation

Did You Get the Big O Right? NexusBro Will Tell You in Seconds.

Complexity Analysis

Testing Your Implementation

Python-Specific Optimizations

Unlock Unlimited QA Audits for $15.99/mo

Frequently Asked Questions

Share this article

Related Articles

Unlock Unlimited QA Audits for $15.99/mo

Is your site built to last?

How does your site compare?

Explore More Topics

The Complete Guide to Python Variables

The Complete Guide to TypeScript Strict Mode

The Complete Guide to Swift Optionals

The Complete Guide to SELECT Queries

The Definitive Git Basics Guide for Developers

The Complete PHP Fundamentals Developer Guide

Key Takeaways

Union-Find (Disjoint Set) in Python: Overview

Python Implementation

Step-by-Step Explanation

Did You Get the Big O Right? NexusBro Will Tell You in Seconds.

Complexity Analysis

Testing Your Implementation

Python-Specific Optimizations

Unlock Unlimited QA Audits for $15.99/mo

Frequently Asked Questions

Share this article

Related Articles

Unlock Unlimited QA Audits for $15.99/mo

Is your site built to last?

How does your site compare?

Explore More Topics

The Complete Guide to Python Variables

The Complete Guide to TypeScript Strict Mode

The Complete Guide to Swift Optionals

The Complete Guide to SELECT Queries

The Definitive Git Basics Guide for Developers

The Complete PHP Fundamentals Developer Guide