Union Find (Disjoint Set Union)

Union-Find, also known as Disjoint Set Union (DSU), is a data structure for solving graph connectivity problems like checking whether two nodes are connected, detecting cycles, or grouping elements efficiently.

Using union find, we can easily tell whether two elements belong to the same group and if not, it lets us merge groups together.

In this chapter, I’ll cover:

What Union-Find is and how it works
The two core operations: find and union
Key optimizations like path compression and union by rank/size that make union find operations run in nearly constant time

What is Union Find?

Union-Find is a data structure that helps us manage a collection of elements divided into disjoint sets meaning no two sets overlap.

Loading simulation...

Every element belongs to exactly one set, and sets can be merged when a connection is discovered.

Union-Find supports two fundamental operations:

Find

This operation tells us which set an element belongs to by returning the root representative of that set.
For example, if Alice and Bob are in the same friend circle, find(Alice) and find(Bob) will return the same root.

Union

This operation merges two sets into a single set.
If Alice’s group and Charlie’s group are separate but they become friends, the union operation connects them into one larger group.

Basic Implementation

The simplest way to represent Union-Find is with an array called parent.

We start by initializing the parent array. Initially, every node is its own parent, meaning each element is its own set
The find operation walks up the parent chain until it reaches the root. That root represents the set that the element belongs to.
The union operation finds the roots of each element. If they’re different, the elements are in different sets, so we merge them by pointing one root to the other.

Step 1: Initialization

Step 2: Find Operation

Step 3: Union Operation

Example Walkthrough

Consider 5 elements: [0, 1, 2, 3, 4].

Initially, each is its own parent.
After union(0, 1), elements 0 and 1 share the same root.
After union(2, 3), elements 2 and 3 share the same root.
If we now call find(1) and find(0), they’ll both return 0, meaning they’re in the same set.

In this basic version:

Find is O(h), where h is the height of the tree formed by parent pointers.
Union is also O(h), since it calls find.

The basic implementation of Union-Find works, but it can get slow if the parent pointers form tall chains. In the worst case, operations can take O(n) time.

Optimizations

To fix this, we use two optimizations: Path Compression and Union by Rank (or Size).

With both applied, find and union run in amortized O(α(n)) time, where α is the inverse Ackermann function. The bound is per-operation amortized, not worst-case: a single find may still walk a long chain, but the path compression it performs flattens the structure so the total cost of any sequence of m operations on n elements is O(m · α(n)). For every n that fits in memory, α(n) ≤ 4, so this is effectively constant on average.

1. Path Compression

Path compression flattens the structure of the tree whenever we call find.

Normally, find(x) climbs one parent at a time until it reaches the root.
With path compression, we make every visited node point directly to the root.
This way, future queries become much faster.

Consider a long chain of 10 nodes. Without path compression, find walks through all 10 nodes every time. With path compression, after one find call every node on that path points directly to the root, so later finds on those nodes run in O(1).

2. Union by Rank (or Size)

This optimization keeps the tree shallow when merging sets.

Rank is the approximate height of the tree.
When uniting two roots, attach the shorter tree under the taller one. Attaching the taller tree under the shorter one would add a level and make the result deeper, so we avoid that.
If both roots have the same rank, pick one as the new root and increase its rank by one.
By always keeping the taller tree as the parent, the overall height grows slowly, which keeps find fast.

When path compression and union by rank are used together, find and union run in amortized O(α(n)) time per operation, which is effectively constant for any practical input size.

Complexity Analysis

Time Complexity

The naive implementation runs find and union in O(n) in the worst case, because the parent pointers can form a single tall chain that find must walk from end to root. Adding path compression and union by rank or size together changes this picture: each operation runs in O(α(n)) amortized, where α is the inverse Ackermann function. For any input size that fits in memory, α(n) stays at or below about 4, so each operation is effectively constant. A sequence of m operations on n elements runs in O(m · α(n)).

Space Complexity

The space cost is O(n) for the parent array, plus another O(n) for the rank or size array, giving O(n) overall.

Key Takeaways

Union-Find, also called Disjoint Set Union, manages a collection of elements split into disjoint sets and answers connectivity questions through two operations: find returns the root representative of an element's set, and union merges two sets into one.
The basic implementation stores a parent array where each element starts as its own parent, find walks up the parent chain to the root, and union points one root at the other; both run in O(h) time, which degrades to O(n) when the parent pointers form a tall chain.
Path compression speeds up find by making every node visited on the way to the root point directly to that root, so repeated queries on those nodes run in O(1).
Union by rank keeps trees shallow by attaching the shorter tree under the taller one, and when both roots share the same rank it picks one as the new root and increases its rank by one.
Combining path compression with union by rank brings find and union to amortized O(α(n)) per operation, where α is the inverse Ackermann function that stays at or below 4 for any n that fits in memory, making the operations effectively constant on average.

Quiz

Introduction Quiz

10 quizzes

Introduction to Union Find