☕ Buy me a coffee — $3

Union-Find Data Structure

Overview

The Union-Find data structure, also known as Disjoint Set Union (DSU), is a powerful data structure used to efficiently manage and query disjoint sets. It provides an elegant solution for tracking which elements belong to the same set and for merging sets together. The data structure maintains a collection of disjoint (non-overlapping) sets and supports two fundamental operations:

  • Find: Determines the representative (root) of the set to which a particular element belongs. This operation answers the question: "Which set does this element belong to?"
  • Union: Merges two sets into one by connecting their roots. This operation combines two separate sets into a single set.

The Union-Find data structure uses a tree-based representation where each set is represented as a tree, with one element serving as the root (representative) of that set. Initially, each element is its own parent, forming n singleton sets. The Find operation traverses up the tree to find the root, while Union connects two trees by making one root point to the other.

History and the Inverse Ackermann Miracle

The basic Union-Find data structure was described by Bernard Galler and Michael Fischer in 1964 in a paper titled "An improved equivalence algorithm." The name "disjoint-set union" came later; the basic construction, each element points to a representative, with the representative pointing to itself, was already in wide use in the compiler community for tracking equivalence classes of program variables.

The theoretical significance of Union-Find lies in a remarkable analytical result established over the following decade. In 1975, Robert Tarjan proved that Union-Find with both path compression and union by rank achieves amortised time per operation of O(α(n)), where α is the inverse of the Ackermann function, a function that grows so slowly that for any conceivable input size (up to and beyond the number of atoms in the observable universe), α(n) stays at or below 4. Tarjan's bound was tight: he also proved in 1979 that no pointer-based data structure supporting Union and Find can achieve better than Θ(α(n)) amortised per operation in the worst case. This is one of the most beautiful matching upper and lower bounds in the algorithms literature.

The Ackermann function is one of the fastest-growing functions in mathematics, its values dwarf any polynomial, exponential, or tower of exponentials. So its inverse grows breathtakingly slowly. For all practical purposes, α(n) = O(1). This means that for any input you will ever encounter, Union-Find behaves as though it were constant-time per operation, despite the theoretical bound being technically super-constant.

The Design Space: Union by Rank vs. Size, Path Compression vs. Path Halving

The classical Union-Find has two optimisations, and there are meaningful alternatives for each.

Union by Rank vs. Union by Size

Union by rank uses an upper bound on the tree's height, updated only when trees of equal rank are merged. Union by size tracks the number of nodes in each tree, and always attaches the smaller tree to the larger. Both achieve the same asymptotic O(α(n)) with path compression. Union by size is often preferred because the size array is directly useful, it lets you answer "how big is this component?" in O(α(n)), which rank cannot. Most modern implementations use union by size for exactly this reason.

Path Compression Variants

Full path compression (shown in the recursive implementation above) walks up to the root, then makes every node on the path point directly to the root on the way back down. This is optimal in the sense that a subsequent Find on any of those nodes is O(1).

Path halving makes every node on the path point to its grandparent as we walk up. It flattens the tree less aggressively, but does not require the two-pass traversal, and is iterative so it avoids recursion-limit problems on deep trees. Path halving achieves the same O(α(n)) amortised bound and is often faster in practice on modern hardware because of better cache behaviour.

Path splitting makes each node on the path point to its grandparent, similar to halving but visiting every node instead of every other. Also O(α(n)).

All three compression variants achieve the same asymptotic bound when combined with either union-by-rank or union-by-size. On real inputs the differences are small but measurable: iterative path halving with union by size is usually the fastest combination in practice, and is what most competitive-programming templates use.

Where Union-Find Is Essential

Kruskal's Minimum Spanning Tree

Kruskal's algorithm sorts edges by weight and greedily adds each edge if it does not form a cycle. "Does it form a cycle" is exactly the Union-Find query "are these two vertices in the same component?" This is where most people first meet Union-Find in an algorithms course. Kruskal's would be an intellectual curiosity without Union-Find; with it, it runs in O(E log E) and is a practical MST algorithm.

Percolation and Physical Simulation

The percolation problem asks: given a grid where each cell is "open" with probability p, is there a path of open cells from top to bottom? This is a classical problem in statistical physics with applications to fluid flow through porous media, forest fire spread, and electrical conductivity of composite materials. Union-Find lets you simulate percolation efficiently by unioning adjacent open cells and querying whether the top row is in the same component as the bottom row.

Dynamic Connectivity in Networks

A network administrator asks: "if I add this cable, will it complete a spanning circuit?" Union-Find answers the query in effectively constant time. Combined with offline preprocessing (processing all queries together and running them in a carefully chosen order), Union-Find handles a range of problems that would otherwise require more expensive graph algorithms.

Image Segmentation and Connected-Component Labelling

Given a binary image (each pixel is 0 or 1), find all connected components of 1-pixels. The classical two-pass algorithm uses Union-Find to merge components as they are discovered during a scan, and then to assign a canonical label to each pixel in a second pass. Every image-processing library from OpenCV to scikit-image uses a variant of this.

Type Inference in Compilers

Union-Find is at the heart of the Hindley–Milner type inference algorithm used by ML, Haskell, OCaml, Rust and many other statically-typed languages. Each type variable is a node; when the type checker unifies two variables, it calls union on them. When it needs to know the current type of a variable, it calls find. This is one of the most important non-graph applications of Union-Find and a good example of how the same abstraction shows up in unexpected places.

Offline LCA and Range Queries

Tarjan's offline lowest-common-ancestor algorithm processes a batch of LCA queries in O((V + Q) α(V + Q)) using Union-Find, faster than the online O((V + Q) log V) using binary lifting. Similar Union-Find tricks appear in offline query problems throughout competitive programming.

Key Optimizations

To achieve near-constant time complexity, Union-Find employs two key optimizations:

  • Path Compression: During the Find operation, all nodes along the path from the queried element to the root are directly connected to the root. This flattens the tree structure, making future Find operations faster.
  • Union by Rank: When merging two sets, the smaller tree (by rank/height) is attached to the root of the larger tree. This prevents the tree from becoming too tall, keeping operations efficient.

With these optimizations, both Find and Union operations achieve nearly constant amortized time complexity, approximately O(α(n)), where α(n) is the inverse Ackermann function, which grows extremely slowly and is effectively constant for all practical purposes. The space complexity is O(n) to store the parent and rank arrays.

How It Works

Union-Find works by:

  1. Initialization: Each element starts as its own parent, creating n singleton sets
  2. Find Operation: Traverses up the tree to find the root, applying path compression along the way
  3. Union Operation: Connects two trees by making one root point to the other, using union by rank to keep trees balanced
  4. Path Compression: During Find, all nodes on the path are connected directly to the root

Union-Find Algorithm Pseudocode


Initialize:
    parent = [i for i in range(n)]
    rank = [1] * n

Find(x):
    if x != parent[x]:
        parent[x] = Find(parent[x])  # Path compression
    return parent[x]

Union(x, y):
    root_x = Find(x)
    root_y = Find(y)
    if root_x != root_y:
        if rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        elif rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

Implementation


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

Complexity Analysis

  • Time Complexity:
    • Find: O(α(n)) amortized (nearly constant)
    • Union: O(α(n)) amortized (nearly constant)
    • Without optimizations: O(n) worst case
  • Space Complexity: O(n) - to store parent and rank arrays

The inverse Ackermann function α(n) grows so slowly that it is effectively a constant. It stays at or below 4 for every n up to a tower of exponents far larger than the number of atoms in the observable universe, there is no input you could ever construct for which α(n) exceeds a small single-digit number. Tarjan (1975) proved this bound is tight: no implementation using pointer-based union-find can do asymptotically better.

Limitation: Union-Find Cannot Undo a Union

Union-Find is incremental only. There is no efficient split operation, once two sets are merged, ordinary DSU cannot separate them again, because the tree structure discards the information about which elements came from where. If your problem deletes edges, Union-Find is the wrong data structure.

The alternatives, in increasing order of complexity:

  • Process offline in reverse. If you know all the operations in advance and the only change is deletion, run time backwards, deletions become insertions and plain Union-Find works.
  • Union-Find with rollback. Skip path compression, keep union by rank, and push each parent change onto an undo stack. Operations become O(log n) instead of O(α(n)), but you can revert them. Combined with divide-and-conquer over the timeline, this solves offline dynamic connectivity.
  • Fully dynamic structures. For genuinely online insert-and-delete workloads, use Holm–de Lichtenberg–Thorup (O(log² n) amortized), Euler tour trees, or link-cut trees.

Path Compression Explained

Path compression is a crucial optimization that flattens the tree structure during Find operations. When we find the root of an element, we update all nodes along the path to point directly to the root.

Example: If we have a path A → B → C → D (root), after Find(A), the structure becomes: 

Before:  A → B → C → D
After:   A → D
         B → D
         C → D

This makes future Find operations on A, B, or C much faster.

Union by Rank Explained

Union by rank ensures that when merging two trees, we always attach the smaller tree to the root of the larger tree. This prevents the tree from becoming too tall.

The rank represents an upper bound on the height of the tree. When two trees have the same rank, we increment the rank of the new root.

Example: 

Tree 1 (rank 2):        Tree 2 (rank 1):
      A                       D
     / \                     /
    B   C                    E
   /
  G

After Union(A, D) - lower rank attaches to higher, ranks unchanged:
      A (rank 2)
     /|\
    B C D
   /     \
  G       E

Rank is an upper bound on height, not a node count, two trees with the same shape always have the same rank. The interesting case is the one the code handles specially: when both roots have equal rank, neither is taller, so we pick one arbitrarily and increment its rank, since the merged tree really is one level deeper.

Union by Size: The Common Alternative

Union by size, attach the tree with fewer nodes to the one with more, achieves the same O(α(n)) bound and is often preferred in practice, because the size array is directly useful: it answers "how big is this component?" for free, which rank cannot do. 

def union_by_size(self, x, y):
    root_x, root_y = self.find(x), self.find(y)
    if root_x == root_y:
        return False                      # already connected
    if self.size[root_x] < self.size[root_y]:
        root_x, root_y = root_y, root_x   # ensure root_x is the larger tree
    self.parent[root_y] = root_x
    self.size[root_x] += self.size[root_y]
    return True                           # returns whether a merge happened

Also worth knowing: path halving and path splitting are iterative alternatives to recursive path compression with the same asymptotic bound and no risk of exceeding Python's recursion limit on a deep tree: 

def find_iterative(self, x):
    while self.parent[x] != x:
        self.parent[x] = self.parent[self.parent[x]]   # path halving
        x = self.parent[x]
    return x

Union-Find Framework

  • Initialize the data structure with each element as its own parent and rank set to 1.
  • Use the Find operation to locate the root representative of an element's set.
  • Apply path compression during Find to optimize future queries by flattening the tree structure.
  • Use Union by rank to merge sets efficiently, always attaching the smaller tree to the larger one.
  • Check if elements are in the same set by comparing their root representatives from Find operations.

Example

Using Union-Find to track connected components: 


# Initialize with 5 elements: [0, 1, 2, 3, 4]
uf = UnionFind(5)

# Initially, each element is its own parent
# parent = [0, 1, 2, 3, 4]
# rank = [1, 1, 1, 1, 1]

# Union operations
uf.union(0, 1)  # Connect 0 and 1
uf.union(2, 3)  # Connect 2 and 3
uf.union(1, 2)  # Connect 1 and 2 (connects all 0,1,2,3)

# Find operations
uf.find(0) == uf.find(3)  # True - same component
uf.find(0) == uf.find(4)  # False - different components

Real-World Applications

  • Network Connectivity: Determining if nodes in a network are connected
  • Image Processing: Connected component labeling in images
  • Social Networks: Finding friend groups or communities
  • Kruskal's Algorithm: Building minimum spanning trees
  • Percolation Theory: Modeling physical systems
  • Equivalence Testing: Determining if two elements are equivalent

Related Algorithms

Explore other graph algorithms: