Union-Find: A Deep Dive into Disjoint Set Union

Trying to count islands in a grid using only DFS or BFS feels clunky because you're constantly re-traversing the same landmasses just to see if they're connected. The real "aha!" moment comes when you realize you don't need to walk the whole island; you just need to know if two cells belong to the same group. That's where Union-Find (Disjoint Set Union) saves the day.

At its core, Union-Find solves one problem: "Are these two elements in the same set?" It's like tracking friend circles at a party; as you find out who knows whom, you merge groups. Eventually, you can check if two people are connected without re-scanning the entire room.

The logic is simple:
1. Every element starts as its own parent.
2. Find(x) climbs the parent chain until it hits the root (the representative of the set).
3. Union(x, y) finds the roots of both. If they're different, it links one root to the other.

To stop the parent chains from becoming long, inefficient lines, we use two optimizations: Union by Rank (attaching the shorter tree to the taller one) and Path Compression (making every node on the path point directly to the root during a find operation). This pushes the time complexity down to nearly O(1) in practice.

Here is a clean Python implementation. I've written this to be a practical tutorial for anyone implementing this in a real-world AI workflow or coding challenge.

class UnionFind:
    def __init__(self, n):
        # Each element is its own parent; rank tracks tree depth.
        self.parent = list(range(n))
        self.rank = [0] * n 

    def find(self, x):
        # Path compression: flatten the structure as we search.
        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 the same set
        
        # Union by rank: attach shorter tree to taller tree.
        if self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        elif self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

A few gotchas from my own experience:

• Missing Path Compression: If you forget self.parent[x] = self.find(...), your find operation degrades to O(n), and your performance will tank on large datasets.
• Ignoring Root Checks: If you don't check if rx == ry before merging, you'll waste cycles and potentially mess up your rank tracking.

If you're building an LLM agent that needs to handle graph-based data or clustering, this is a much more efficient pattern than brute-force traversal.