Union‑Find: The Fellowship of the Set

The Quest Begins (The "Why")

I still remember the first time I stared at a LeetCode board full of “connected components” questions and felt like I was trying to herd cats with a spoon. The problem was simple on paper: given N nodes and a list of edges, tell me how many separate groups exist. My first instinct? Run a DFS/BFS from every unvisited node, mark everything reachable, and count the starts. It worked… until the input size blew up to 10⁵ nodes and 2·10⁵ edges. Suddenly my O(N + M) DFS was hidden inside a quadratic nightmare because I was rebuilding visited arrays for each test case in a multi‑test harness. I felt like Frodo staring at the Eye of Sauron—tiny, overwhelmed, and wondering if there was a secret weapon I’d missed.

That’s when I discovered Union‑Find (also called Disjoint Set Union, DSU). It’s not just another data‑structure trick; it’s a way of thinking about connectivity that turns a seemingly repetitive search into almost‑constant‑time merges and queries. Once I got it, the same problem dropped from “I need to traverse the whole graph each time” to “I can answer each edge in practically O(1) time”. It felt like grabbing the One Ring and realizing it actually helps you instead of corrupting you.

The Revelation (The Insight)

What does Union‑Find actually store?

Imagine each element starts in its own solitary clan. We keep an array parent[i] that points to the “representative” (or root) of the clan that i belongs to. If i is a root, parent[i] == i.

When we get an edge (u, v), we ask: are u and v already in the same clan? If yes, nothing changes. If not, we merge the two clans by making one root point to the other.

Why does this work so fast?

Two simple heuristics turn what could be a linear chain into a practically flat tree:

1. Union by rank/size – always attach the smaller tree under the larger one. This guarantees that the depth of any tree grows at most logarithmically with the number of unions.
2. Path compression – whenever we look up a root, we make every node on the way point directly to that root. After a few finds, the tree becomes almost flat, giving us the famous inverse Ackermann bound, α(N), which is < 5 for any realistic N.

In plain English: every time we ask “who’s your leader?” we shortcut the path, and we never let the trees get lopsided. The result? Almost‑constant time per operation, which in interview land we treat as O(N) for a sequence of N unions/finds.

The “aha!” moment

I was implementing a naïve union (just parent[pu] = pv) and kept getting TLE on a large test. I added path compression on a whim, and the runtime dropped from 2.3 seconds to 0.07 seconds. I literally shouted “This is awesome!” at my screen—felt like I’d just unlocked a secret level in a game.

Wielding the Power (Code & Examples)

Below is a compact, battle‑tested Union‑Find class in Python. I’ve added comments that point out the two traps that bite most newcomers.

class UnionFind:
    def __init__(self, n):
        # parent[i] = i means i is its own root
        self.parent = list(range(n))
        # rank approximates tree depth; size works just as well
        self.rank = [0] * n
        self.components = n          # handy: number of distinct sets

    def find(self, x):
        # Path compression: make every node on the route point to root
        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 together → no merge
        # Union by rank: attach smaller rank under larger rank
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx            # ensure rx has higher rank
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.components -= 1
        return True

Common mistake #1 – Forgetting path compression

If you implement find as a simple loop without updating parents, each find can walk up a chain of length O(log N) (thanks to union by rank) but never gets better. In pathological cases (e.g., many unions followed by many finds) you’ll hit O(N log N) overall—still okay for small N but a sure TLE on LeetCode’s larger tests. The one‑liner self.parent[x] = self.find(self.parent[x]) is the magic fix.

Common mistake #2 – Union by rank vs. size confusion

Some folks swap the rank comparison or forget to increment rank when the trees are equal. The symptom? The tree depth can grow linearly, turning finds into O(N). Keep the rule: attach the lower‑rank root under the higher‑rank root; increase rank only when they were equal.

---

Example 1 – LeetCode 323: Number of Connected Components

Given n nodes labeled 0 … n‑1 and a list of undirected edges, return the number of connected components.

Naïve DFS approach (struggle): run a DFS from each unvisited node, O(N + M) per test case—fine for a single case but annoying when the harness runs many cases.

Union‑Find solution (victory):

def countComponents(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.components

Each edge triggers an almost‑constant union. After processing all edges, uf.components holds the answer. Runtime: O(N + M · α(N)) ≈ O(N + M). Memory: O(N).

---

Example 2 – LeetCode 547: Friend Circles

There are N students. A direct friendship is represented by M[i][j] = 1. A friend circle is a group of students who are direct or indirect friends. Return the total number of friend circles.

The matrix is just an adjacency list in disguise.

def findCircleNum(M):
    n = len(M)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i+1, n):
            if M[i][j]:
                uf.union(i, j)
    return uf.components

Again, we only pay for each 1 in the matrix. The elegance shines: no recursion depth worries, no visited array resets—just a tidy loop over the matrix.

---

Why This New Power Matters

Union‑Find turns any problem that asks “are these items in the same group?” or “how many groups exist?” into a near‑constant‑time operation. Think of dynamic connectivity: you can add edges on the fly and instantly query connectivity, which is the backbone of algorithms like Kruskal’s MST, percolation, and even some network‑flow tricks.

In an interview, showing you know the why (rank + path compression) signals that you don’t just memorize code—you understand the invariants that make it fast. It’s a signal that you can take a seemingly messy graph problem and distill it to a clean array‑based solution.

Your Next Quest

I dare you to take a problem you’ve solved with DFS/BFS and rewrite it with Union‑Find. Try LeetCode 721: Accounts Merge—you’ll need to union email strings, map them to indices, and then retrieve the groups. Or, if you’re feeling adventurous, implement a dynamic connectivity structure that supports both adding edges and removing them (hint: you’ll need a rollback or divide‑and‑conquer technique).

Drop your solution in the comments, share aha‑moments, or ask where you got stuck. Let’s keep the fellowship growing—one union at a time! 🚀