Union-Find: The Fellowship of the Sets

The Quest Begins (The "Why")

I still remember the first time I saw LeetCode 323 “Number of Connected Components in an Undirected Graph”. I stared at the adjacency list, thought “I’ll just run a DFS from every node”, and coded it up in ten minutes. The solution passed the easy tests, but when the hidden test cases hit a graph with 10⁵ nodes and 10⁵ edges, my DFS started to choke—stack overflows, repeated visits, and a sinking feeling that I was brute‑forcing a problem that deserved a smarter tool.

That night, after a few too many coffees, I stumbled upon a tiny comment in a discussion thread: “Union‑Find can do this in almost O(1) per operation”. My curiosity sparked like a power‑up in a retro arcade game. I had to know why this seemingly simple data structure could turn a nightmare into a breeze.

The Revelation (The Insight)

At its heart, Union‑Find (aka Disjoint Set Union, DSU) maintains a collection of elements partitioned into disjoint subsets. It supports two operations:

• Find(x) – returns the representative (root) of the set containing x.
• Union(x, y) – merges the sets containing x and y.

The magic lies in two simple heuristics:

1. Path Compression – when we walk up the tree to find a root, we make every node on that path point directly to the root. Future finds become flat, almost constant‑time.
2. Union by Rank/Size – we always attach the smaller tree under the root of the larger one, keeping the overall tree shallow.

Why does this give us near‑O(1) amortized time? Think of each Find as paying a small “tax” to flatten the path. The tax is paid only a few times per node before it becomes a direct child of the root. Over a sequence of m operations, the total work is bounded by O(m α(n)), where α is the inverse Ackermann function—so slow‑growing it’s practically a constant for any realistic n.

In plain English: every time we climb up, we leave a shortcut behind. The next climber benefits from that shortcut, and the structure keeps getting better. It’s like building a network of teleporters while you explore a dungeon—each trip makes the next one faster.

Wielding the Power (Code & Examples)

The Struggle: Naïve DFS

def count_components_dfs(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n
    def dfs(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)

    components = 0
    for i in range(n):
        if not visited[i]:
            dfs(i)
            components += 1
    return components

The DFS works, but for large graphs we allocate an adjacency list, risk recursion depth, and revisit edges many times when we call dfs from each new component.

The Victory: Union‑Find

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * n          # stores tree depth (rank)

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False               # already in same set
        # union by rank
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx            # ensure rx has larger rank
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

def count_components_uf(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    # count distinct roots
    return sum(1 for i in range(n) if uf.find(i) == i)

What changed?

• No adjacency list → O(n) extra space only for parents and ranks.
• Each edge triggers a single union (amortized α(n)).
• The final pass is a simple loop over n nodes. Overall time: O(n + m·α(n)) → practically linear. Space: O(n).

Two Interview Flavors

1. Number of Connected Components (LeetCode 323) – exactly the function above.

2. Accounts Merge (LeetCode 721) – we treat each email as a node; union all emails belonging to the same account, then collect groups by root.

def accountsMerge(accounts):
    email_to_id = {}
    id_to_email = []
    uf = UnionFind(len(accounts))

    for i, (name, *emails) in enumerate(accounts):
        for email in emails:
            if email not in email_to_id:
                email_to_id[email] = len(id_to_email)
                id_to_email.append(email)
            uf.union(email_to_id[emails[0]], email_to_id[email])

    groups = {}
    for email, idx in email_to_id.items():
        root = uf.find(idx)
        groups.setdefault(root, []).append(email)

    res = []
    for root, emails in groups.items():
        name = accounts[root][0]          # any account in the component has the same name
        res.append([name] + sorted(emails))
    return res

Again, the heavy lifting is done by Union‑Find; the rest is just bookkeeping.

Why This New Power Matters

Mastering Union‑Find feels like unlocking a secret spellbook. Suddenly, problems that looked like tangled graphs—friend circles, redundant connections, image segmentations, Kruskal’s MST—become a few lines of clean code. You stop worrying about recursion limits or massive adjacency matrices and start focusing on the logic of merging sets.

The best part? The idea is tiny enough to explain in a coffee break, yet powerful enough to dominate hard interview rounds. Once you’ve internalized path compression and union by rank, you start spotting opportunities everywhere: “Hey, this is just a Union‑Find problem in disguise!”

Your Next Quest

Grab a fresh LeetCode challenge—maybe 547. Number of Provinces or 128. Longest Consecutive Sequence—and try solving it first with a naïve BFS/DFS, then refactor with Union‑Find. Feel the speed difference, share your benchmark, and celebrate when the runtime drops from seconds to milliseconds.

Go forth, fellow adventurer, and may your sets always stay united! 🚀