Disjoint Set / Union-Find

Also Known As

TL;DR

Explanation

Disjoint Set (Union-Find) maintains a forest of trees where each tree represents a set. find(x) returns the root of x's tree (the set representative). union(x, y) merges the two sets. Optimisations: path compression (flatten tree on find), union by rank (always attach smaller tree to larger). Combined: near-O(1) amortised — technically O(α(n)) where α is the inverse Ackermann function, practically constant. Applications: Kruskal's Minimum Spanning Tree, network connectivity (are A and B in the same network?), image segmentation, and cycle detection in undirected graphs.

Common Misconception

Why It Matters

Common Mistakes

• Not implementing path compression — find() is O(n) without it.
• Not using union by rank — trees become linked lists without it.
• Using for directed graphs — Union-Find tracks connected components in undirected graphs only.
• Forgetting that find() modifies the structure (path compression) — not purely read-only.

Code Examples

// No optimisations — O(n) find:
class NaiveUnionFind {
    private array $parent;
    public function find(int $x): int {
        while ($this->parent[$x] !== $x) {
            $x = $this->parent[$x]; // Walk up — O(n) in worst case
        }
        return $x;
    }
}

// Path compression + union by rank — O(alpha n) amortised:
class UnionFind {
    private array $parent;
    private array $rank;

    public function __construct(int $n) {
        $this->parent = range(0, $n - 1);
        $this->rank   = array_fill(0, $n, 0);
    }

    public function find(int $x): int {
        if ($this->parent[$x] !== $x)
            $this->parent[$x] = $this->find($this->parent[$x]); // Path compression
        return $this->parent[$x];
    }

    public function union(int $x, int $y): void {
        $rx = $this->find($x); $ry = $this->find($y);
        if ($rx === $ry) return;
        if ($this->rank[$rx] < $this->rank[$ry]) [$rx, $ry] = [$ry, $rx];
        $this->parent[$ry] = $rx;
        if ($this->rank[$rx] === $this->rank[$ry]) $this->rank[$rx]++;
    }
}

References

• ↗ https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Tags

Related Terms