Union-Find

Union-Find is a data structure for maintaining disjoint sets. It supports finding an element’s representative and unioning two groups.

It is especially useful for connectivity problems where edges are added over time.

Core Idea

Each element points to a parent. A representative, or root, identifies the whole group. find(x) returns the representative for x. union(a, b) merges the groups containing a and b.

If two elements have the same representative, they are in the same group.

Class Contract

UnionFind(size) creates size separate groups numbered from 0 through size - 1.

find(x) returns the representative of x’s current group. union(a, b) merges the two groups and returns whether a merge actually happened in the optimized version.

Python Example

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
 
    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a

This basic version shows the interface before optimizations.

How Find Represents Groups

The root of a parent tree is the representative. If find(2) and find(5) return the same root, then 2 and 5 are in the same group.

The representative does not usually matter as a meaningful value. It is just a stable identifier for the group.

Optimized Version

Practical Union-Find usually includes path compression and union by size:

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.size = [1] * size
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
 
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
 
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        return True

Returning False when the roots match is useful for cycle detection.

Complexity

With path compression and union by size or rank, operations are effectively constant for practical algorithm constraints. More precisely, they are amortized inverse-Ackermann time, which grows extremely slowly.

Common Confusions

Union-Find answers connectivity membership. It does not tell the actual path between two vertices.

The basic version can become slow if parent chains become long. Practical versions add path compression and union by rank or size.

Another common mistake is calling union(a, b) and assuming a becomes the root. The root choice is an implementation detail.

When To Use It

Use Union-Find for dynamic connectivity, cycle detection in undirected edge processing, Kruskal’s algorithm, and grouping problems where merges are frequent.

Do not use Union-Find for directed reachability or shortest path problems.

The Main Point

Union-Find represents each group by a root. Efficient versions make find paths short and merge smaller structures into larger ones.