Disjoint Set (Union-Find)Disjoint Set (Union-Find)

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

A disjoint-set structure — also called union-find or a merge-find set — tracks a partition of a set: a collection of elements split into non-overlapping groups, where every element belongs to exactly one group. It answers exactly two questions and does nothing else:

• find(x) — which group is x in?
• union(a, b) — merge the group containing a with the group containing b.

That is a tiny interface, and its narrowness is the whole point. Union-find is the answer to “are these two things connected?” when the connections keep arriving and never go away. Most graph structures answer connectivity by traversing — a BFS or DFS from a costs O(V + E) every time you ask. Union-find answers the same question in effectively constant time, because it never traverses anything: it maintains the answer incrementally as edges arrive.

The remarkable part is the complexity. With two small optimizations — union by rank/size and path compression — a sequence of m operations over n elements costs O(m · α(n)), where α is the inverse Ackermann function. α(n) grows so slowly that it is at most 4 for any n you could physically store, so in practice each operation is constant time. Robert Tarjan proved in 1975 that this bound is tight — no pointer-based structure can do better — which makes union-find one of the few data structures whose optimality is settled.

Its most famous customer is Kruskal’s algorithm for minimum spanning trees (see ./15-minimum-spanning-trees.md), but it turns up wherever “merge these two groups” is the natural operation: connected components, cycle detection in undirected graphs, image segmentation, percolation, “number of islands” grid problems, and equivalence-class bookkeeping in type checkers and compilers.

Fundamentals

The model: a partition of a set

Formally, given a universe S = {0, 1, …, n−1}, a partition is a family of subsets S₁, S₂, …, S_k such that every S_i is non-empty, no two overlap, and their union is S. Union-find maintains such a partition under merges.

Each subset elects a representative (or leader, or root) — one arbitrary member that stands for the whole set. find(x) returns the representative of x’s set, and the entire contract of the structure follows:

a and b are in the same set if and only if find(a) == find(b).

This is why find returning “some element” rather than “a set id” is enough. You never need to enumerate a set’s members to compare two sets; you compare their leaders.

The three primitive operations are:

Note what is missing: there is no split, no delete, no way to remove an element from a set. Union-find is monotone — sets only ever merge, never break apart. That restriction is what buys the speed, and it is the first thing to check when deciding whether the structure fits your problem.

The forest representation

The standard implementation stores the partition as a forest: one tree per set, with the root being the representative. A single integer array parent[] is enough — parent[x] is x’s parent, and a root points at itself.

parent = [0, 0, 1, 1, 4, 4, 5]

        0            4
       / \          / \
      1   ...      5   ...
     / \           |
    2   3          6

find(3) walks 3 → 1 → 0, returns 0
find(6) walks 6 → 5 → 4, returns 4
find(3) != find(6), so 3 and 6 are in different sets

The tree shape here has nothing to do with the graph being modelled. It is purely an internal bookkeeping structure: the edges of the forest are “who told me my leader”, not edges of the input graph. This is worth internalizing, because it explains why the forest can be reshaped freely (path compression does exactly that) without changing any answer.

The naive implementation, and why it is O(n)

The obvious version does no balancing at all: find walks to the root, union hangs one root under the other.

class NaiveDisjointSet:
    """Union-Find with no optimizations. Correct, but degenerates to a linked list."""

    def __init__(self, n):
        self.parent = list(range(n))       # every element starts as its own root

    def find(self, x):
        while self.parent[x] != x:         # walk up — costs O(height of the tree)
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            self.parent[rb] = ra           # arbitrary: b's root goes under a's root

The problem is that union picks arbitrarily, and an adversarial (or merely unlucky) order of merges builds a path, not a bush:

ds = NaiveDisjointSet(n)
for i in range(1, n):
    ds.union(i, i - 1)      # each step buries the whole existing chain one level deeper

after union(1,0), union(2,1), union(3,2), union(4,3):

    0 → 1 → 2 → 3 → 4        (parent chain; 4 is the root)

find(0) now costs 4 pointer hops. With n elements, it costs n−1.

The forest has become a linked list of height n−1, so find is O(n) and a sequence of m operations is O(m·n). That is worse than just running a BFS. Both optimizations below exist to prevent exactly this shape.

Optimization 1 — union by rank / union by size

The fix for the chain is to stop choosing arbitrarily. When merging two trees, attach the shorter one under the taller one (union by rank) or the smaller one under the bigger one (union by size). Either way the deep tree keeps its root and its height does not grow.

• Union by size — store size[r] = number of elements in the tree rooted at r. Attach the smaller root under the larger.
• Union by rank — store rank[r] = an upper bound on the tree’s height. Attach the lower-rank root under the higher-rank one; if ranks tie, pick either and increment the winner’s rank by 1.

Both give the same asymptotic guarantee: height ≤ log₂ n. The argument for union by size is a one-liner and worth remembering — a node’s depth increases only when its tree is the smaller side of a merge, and that at least doubles the size of the tree it lives in. A tree of n elements can double at most log₂ n times, so no element can be pushed down more than log₂ n times.

In practice union by size is slightly preferable: the size counter is useful in its own right (component sizes, largest-component queries) and it stays exact, whereas rank becomes only an upper bound once path compression starts flattening trees.

With this alone, find and union are O(log n) worst case — already usable, and importantly it holds per operation, not just amortized.

Optimization 2 — path compression

Union by rank stops trees from getting deep. Path compression makes them get shallow: after find(x) has walked from x to the root, it walks the path again and points every node it passed directly at the root.

before find(6):          after find(6):

      0                        0
      |                     /  |  \
      3                    3   5   6
      |
      5
      |
      6

one walk of length 3 pays for all future finds on 3, 5, 6 — each now costs 1 hop

Nothing about the partition changes — every node on the path had the same root before and after. Only the bookkeeping got cheaper. This is the key insight that makes the flattening obviously safe.

Path compression alone (without union by rank) also gives O(log n) amortized, but its real power appears only in combination with balancing.

The combined bound — O(α(n)) and what α is

With both union by rank/size and path compression, Tarjan showed that any sequence of m operations on n elements costs O(m · α(n)) total, where α is the inverse Ackermann function.

The Ackermann function A(m, n) is the textbook example of a function that is computable but grows faster than any primitive recursive function — faster than exponential, faster than tower-of-exponentials, faster than anything with a name. A common variant:

A(0, n) = n + 1
A(m, 0) = A(m − 1, 1)
A(m, n) = A(m − 1, A(m, n − 1))

A(1, n) ≈ n + 2
A(2, n) ≈ 2n + 3
A(3, n) ≈ 2^(n+3) − 3
A(4, 2) = 2^2^2^2^2 − 3 ≈ 2 × 10^19728     ← already far beyond the number of atoms in the universe

α(n) is its inverse: roughly, the smallest k such that A(k, k) ≥ n. Because A explodes, α crawls:

So for every input that fits in a computer — every input that will fit in every computer ever built — α(n) ≤ 4. Union-find is not literally O(1); it is provably not O(1) (Tarjan and van Leeuwen proved a matching Ω(m α(n)) lower bound for this class of structures). But the difference between α(n) and a constant is unobservable, and it is entirely fair to reason about union-find as constant time when budgeting an algorithm. Kruskal’s O(E log E) cost is dominated by the sort, not by the union-find.

Full implementation

class DisjointSet:
    """Union-Find over integers 0..n-1, with union by size and path compression.

    All operations are O(alpha(n)) amortized, which is <= 4 for any realistic n.
    Space is O(n): two integer arrays.
    """

    def __init__(self, n):
        self.parent = list(range(n))    # parent[x] == x means x is a root
        self.size = [1] * n             # size[r] is meaningful only when r is a root
        self.components = n             # number of disjoint sets right now

    def find(self, x):
        """Return the representative of x's set, compressing the path on the way."""
        root = x
        while self.parent[root] != root:        # pass 1: locate the root
            root = self.parent[root]
        while self.parent[x] != root:           # pass 2: repoint everything at it
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        """Merge the sets of a and b. Return False if they were already the same set."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:       # smaller tree goes under the bigger one
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def set_size(self, x):
        """Number of elements in x's set — O(alpha(n)), thanks to the size array."""
        return self.size[self.find(x)]

Two implementation notes that matter in real code:

Iterative find, not recursive. The recursive form is prettier —

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])   # compress on the way back up
    return self.parent[x]

— but on a freshly built structure the first find can recurse O(log n) deep, and in Python (default recursion limit 1000) or on a constrained stack that is a real crash risk for large n. The two-pass iterative version has no such limit.

Path halving is a cheaper single-pass alternative that gives the same asymptotic bound and is what most competitive-programming templates use:

def find(self, x):
    while self.parent[x] != x:
        self.parent[x] = self.parent[self.parent[x]]   # point x at its grandparent
        x = self.parent[x]
    return x

It halves the path length on every traversal instead of flattening it completely, in one pass with no second loop and no extra memory. In benchmarks it is usually the fastest of the three.

Complexity summary

Note where “amortized” is load-bearing: a single find on a compressed structure can still cost O(log n) (it may be the traversal that does the flattening). It is the sequence that is near-constant. For hard real-time systems where per-operation latency matters more than throughput, union by rank alone gives a worst-case O(log n) guarantee with no amortization.

Key Concepts

Application 1 — Kruskal’s minimum spanning tree

This is the canonical use. Kruskal’s algorithm sorts edges by weight and greedily accepts each one unless it would close a cycle. “Would it close a cycle?” is exactly “are these two endpoints already connected?”, which is exactly find(u) == find(v).

def kruskal(n, edges):
    """MST of a connected graph on n vertices.

    edges: list of (weight, u, v). Returns (total_weight, chosen_edges).
    Complexity: O(E log E) for the sort, plus O(E * alpha(V)) for the union-find,
    so the sort dominates.
    """
    ds = DisjointSet(n)
    total, chosen = 0, []
    for w, u, v in sorted(edges):          # ascending weight
        if ds.union(u, v):                 # union returns False if u,v already connected
            total += w
            chosen.append((w, u, v))
            if len(chosen) == n - 1:       # a spanning tree on n vertices has n-1 edges
                break
    return total, chosen


edges = [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3)]
print(kruskal(4, edges))     # (6, [(1, 0, 1), (2, 1, 3), (3, 1, 2)])

The if ds.union(...) idiom — where union returns whether it actually merged anything — is the reason union should return a boolean rather than None. It saves a redundant pair of find calls and reads exactly like the algorithm’s English description. See ./15-minimum-spanning-trees.md for Kruskal in context and its comparison with Prim’s algorithm.

Application 2 — connected components and incremental connectivity

If you build the graph edge by edge and need to answer “is a reachable from b?” at arbitrary points during construction, union-find is the right tool and BFS is not. ds.components gives the number of connected components for free, updated on every merge.

def component_count(n, edges):
    ds = DisjointSet(n)
    for u, v in edges:
        ds.union(u, v)
    return ds.components


def largest_component(n, edges):
    ds = DisjointSet(n)
    for u, v in edges:
        ds.union(u, v)
    return max(ds.set_size(x) for x in range(n))

This is incremental (or partially dynamic) connectivity: edges are added, never removed. If edges can also be deleted, union-find does not work — there is no way to un-merge, because path compression has destroyed the information about which merge put each node where. Fully dynamic connectivity needs Euler-tour trees or link-cut trees, or, if all the queries are known in advance, the offline dynamic connectivity trick: a segment tree over the time axis combined with a rollback DSU (union by size only, no path compression, with a stack of undo records — O(log n) per operation but reversible).

Compare with the traversal-based approach in ./13-graph-data-structures.md: a single DFS labels all components in O(V + E) and is simpler when the graph is static and you only need the labelling once. Reach for union-find when edges stream in, when queries interleave with insertions, or when you are inside Kruskal.

Application 3 — cycle detection in an undirected graph

An undirected edge (u, v) closes a cycle exactly when u and v are already in the same component. So cycle detection is four lines:

def has_cycle(n, edges):
    """True if the undirected simple graph contains a cycle. O(E * alpha(n))."""
    ds = DisjointSet(n)
    for u, v in edges:
        if not ds.union(u, v):     # endpoints were already connected
            return True
    return False

Two caveats. First, this is for undirected graphs only — a directed cycle needs DFS with colouring, or Kahn’s topological sort, because union-find has no notion of edge direction. Second, it assumes a simple graph: a self-loop (u, u) or a repeated edge will be reported as a cycle, which is usually what you want but is worth stating.

A useful corollary: a graph with n vertices is a tree iff it has exactly n − 1 edges, no union call is ever rejected, and ds.components == 1 at the end.

Application 4 — grid problems (“number of islands”)

Grid connectivity problems map onto union-find by flattening the 2-D index: cell (r, c) becomes element r * cols + c.

def count_islands(grid):
    """Count 4-connected groups of '1' cells in a grid of '1'/'0' characters."""
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    ds = DisjointSet(rows * cols)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            # only look up and left: the down/right pairs are handled from the other cell
            for dr, dc in ((-1, 0), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                    ds.union(r * cols + c, nr * cols + nc)

    roots = {ds.find(r * cols + c)
             for r in range(rows) for c in range(cols) if grid[r][c] == '1'}
    return len(roots)


grid = [
    "11000",
    "11000",
    "00100",
    "00011",
]
print(count_islands([list(row) for row in grid]))     # 3

Honest assessment: for the plain “count the islands once” question, a DFS or BFS flood fill is simpler and just as fast (O(rows × cols) either way), and that is what you should write. Union-find earns its place in the dynamic variants — “number of islands II”, where land cells are added one at a time and you must report the island count after each addition. There, flood fill would restart from scratch on every query while union-find just merges with up to four neighbours in O(α).

Union-find also handles the classic percolation problem elegantly: add a virtual “top” node connected to the top row and a virtual “bottom” node connected to the bottom row; the system percolates exactly when ds.connected(top, bottom).

Application 5 — image segmentation

Union-find is the workhorse of two distinct computer-vision tasks:

Connected-component labelling — the binary-image version of the island problem. Scan the image, union each foreground pixel with its already-scanned neighbours, then read off the roots as component labels. The classic two-pass Hoshen–Kopelman algorithm is literally this: pass one assigns provisional labels and records equivalences in a union-find, pass two replaces each provisional label with its find.

Graph-based segmentation (Felzenszwalb–Huttenlocher, 2004) — treat every pixel as a vertex and every adjacent pixel pair as an edge weighted by colour difference. Sort the edges by weight and run something very close to Kruskal: merge two regions only if the edge between them is small relative to the internal variation already present in both. The union-find carries not just the partition but per-region statistics (internal difference, size), which the merge predicate consults:

def should_merge(ds, internal, a, b, weight, k):
    """Felzenszwalb-Huttenlocher merge predicate, sketched.

    internal[r] is the largest edge weight inside region r; k controls the
    preference for larger components (a larger k yields larger regions).
    """
    ra, rb = ds.find(a), ds.find(b)
    if ra == rb:
        return False
    threshold_a = internal[ra] + k / ds.set_size(ra)
    threshold_b = internal[rb] + k / ds.set_size(rb)
    return weight <= min(threshold_a, threshold_b)

The pattern here generalizes well beyond images: union-find with augmented per-set data. Store any aggregate you like (size, sum, min, max, a histogram) on the root only, and update it inside union when the roots merge. It stays correct precisely because only the root’s copy is ever read, and only union ever writes it.

Variant — weighted / parity union-find

The plain structure records “a and b are related”. A weighted (or parity, or DSU with potentials) variant additionally records how they are related, by storing each node’s offset relative to its parent and accumulating offsets during path compression. The parity version answers “is this graph bipartite?” online — the offline version needs a BFS 2-colouring, which cannot handle edges arriving one at a time.

class ParityDisjointSet:
    """Union-Find that also tracks the parity (0/1 colour) of each node vs its root.

    union(a, b) asserts "a and b must have different colours" and returns False
    if that contradicts what is already known — i.e. an odd cycle exists.
    """

    def __init__(self, n):
        self.parent = list(range(n))
        self.rel = [0] * n          # rel[x] = parity of x relative to parent[x]
        self.size = [1] * n

    def find(self, x):
        """Return (root, parity of x relative to root), compressing as we go."""
        if self.parent[x] == x:
            return x, 0
        root, par = self.find(self.parent[x])
        self.parent[x] = root
        self.rel[x] ^= par          # x->root parity = x->parent parity XOR parent->root
        return root, self.rel[x]

    def union(self, a, b):
        ra, pa = self.find(a)
        rb, pb = self.find(b)
        if ra == rb:
            return pa != pb         # already related: consistent only if colours differ
        if self.size[ra] < self.size[rb]:
            ra, rb, pa, pb = rb, ra, pb, pa
        self.parent[rb] = ra
        self.rel[rb] = pa ^ pb ^ 1  # the new edge asserts a and b differ
        self.size[ra] += self.size[rb]
        return True


def is_bipartite(n, edges):
    ds = ParityDisjointSet(n)
    return all(ds.union(u, v) for u, v in edges)


print(is_bipartite(4, [(0, 1), (1, 2), (2, 3), (3, 0)]))     # True  (4-cycle)
print(is_bipartite(3, [(0, 1), (1, 2), (2, 0)]))             # False (triangle)

Replace XOR with modular addition and you get the general “DSU with potentials”, which solves systems of difference constraints (x_a − x_b = d) incrementally and detects contradictions the moment they appear.

Non-integer elements

Everything above assumes elements are 0 .. n−1. For arbitrary hashable objects, map them to integers with a dictionary, or store parent as a dict directly:

class HashDisjointSet:
    """Union-Find over arbitrary hashable elements, created lazily on first use."""

    def __init__(self):
        self.parent = {}
        self.size = {}

    def make_set(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.size[x] = 1

    def find(self, x):
        self.make_set(x)
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

Correct, but noticeably slower: every pointer hop is now a hash lookup rather than an array index, so you lose the cache locality that makes the array version fly (see ./07-hash-tables.md and ./04-arrays.md). When performance matters, do the integer mapping once up front and use the array version.

Best Practices

• Always apply both optimizations. They are four lines of code between them and take the structure from O(n) to effectively O(1). There is no scenario in which the naive version is the right trade-off.
• Prefer union by size over union by rank unless you have a reason not to. It costs the same, and the size array doubles as a component-size query, which you nearly always end up wanting.
• Make union return a boolean saying whether a merge actually happened. It turns Kruskal and cycle detection into one-liners and avoids a duplicate pair of find calls.
• Write find iteratively (two-pass or path halving). The recursive version is elegant but can blow the stack on a large, freshly built structure — and in Python it hits the default recursion limit well before n gets interesting.
• Never read size[x] or rank[x] for a non-root x. Those arrays are only maintained at roots; stale values elsewhere are the single most common union-find bug. Always go through find first.
• Check that your problem is monotone before choosing union-find. Sets only merge. If your problem needs deletion, splitting, or edge removal, you need a different structure (link-cut trees, Euler-tour trees) or the offline segment-tree-on-time technique with a rollback DSU.
• Use a rollback DSU when you need undo, and remember that rollback requires dropping path compression — the flattening is irreversible. That costs you O(log n) per operation instead of O(α(n)), which is almost always an acceptable price.
• Reach for DFS/BFS instead when the graph is static and you need the components once. O(V + E) in one pass, with simpler code and no auxiliary structure. Union-find wins when connectivity queries interleave with edge insertions.
• Attach aggregates to the root, update them in union. Component size, sum, min/max, a counter — all are free if you only read them via find(x) and only write them when two roots merge.
• Do not use union-find for directed reachability. It models an undirected equivalence relation; direction is invisible to it. Directed cycle detection needs DFS colouring or Kahn’s algorithm — see ./13-graph-data-structures.md.
• Say “effectively constant”, not “constant”. O(α(n)) is not O(1), and there is a matching lower bound proving it cannot be. In a complexity budget, treating it as constant is fine; in a written analysis, quoting α correctly shows you know why.

References

• roadmap.sh — Data Structures & Algorithms
• Disjoint-set data structure — Wikipedia
• cp-algorithms — Disjoint Set Union
• Ackermann function — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 19: Data Structures for Disjoint Sets
• Princeton Algorithms — Union-Find (Sedgewick & Wayne)
• VisuAlgo — Union-Find Disjoint Sets
• Kruskal’s algorithm — Wikipedia
• Connected-component labeling — Wikipedia
• Big-O Cheat Sheet