What Are Disjoint Sets?
A Disjoint Set (also known as a Union-Find data structure or Disjoint Set Union / DSU) is a data structure that efficiently manages a collection of elements partitioned into several non-overlapping (disjoint) subsets. It supports two fundamental operations:
- Find: Determine which subset a particular element belongs to. This is typically implemented by returning a representative element (often called the "root" or "parent") for that set.
- Union: Merge two subsets into a single subset. After this operation, the two original sets cease to exist independently and become one combined set.
The data structure is deceptively simple in concept but achieves remarkable efficiency through clever optimizations. It forms the backbone of many graph algorithms and is one of the most elegant examples of how algorithmic improvements can dramatically reduce time complexity.
The Core Idea: Forest of Trees
Internally, a disjoint set is represented as a forest of trees. Each set corresponds to a tree, and the root of that tree serves as the representative element for the entire set. Initially, every element is its own root — a forest of single-node trees. As union operations merge sets together, trees grow larger, and find operations traverse upward from any node to its root to identify the set.
Why It Matters
Disjoint sets are critical in computer science because they solve the dynamic connectivity problem with near-constant time operations. Here are some key applications:
- Kruskal's Minimum Spanning Tree Algorithm: Efficiently checks whether adding an edge would create a cycle in a graph.
- Connected Components in Graphs: Determines which vertices belong to the same connected component.
- Cycle Detection in Undirected Graphs: Quickly identifies cycles as edges are processed.
- Percolation Theory: Models physical systems like water flowing through porous materials.
- Image Segmentation: Groups pixels into regions based on similarity criteria.
- Network Connectivity: Tracks which nodes can reach each other in dynamic networks.
- Symbolic Equivalence Checking: Used in compilers and theorem provers to group equivalent expressions.
Core Operations in Detail
🚀 Deploy your AI agent in 10 minutes
Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.
Try it free →The Find Operation
The find operation takes an element x and returns the root (representative) of the set containing x. In the naive implementation, it recursively follows parent pointers until it reaches a node whose parent is itself. The path from x to the root is traversed each time find is called.
def find(x):
if parent[x] == x:
return x
return find(parent[x])This naive version has a critical weakness: if the tree becomes tall and linear (like a linked list), each find operation takes O(n) time in the worst case, where n is the number of elements.
The Union Operation
The union operation takes two elements and merges their respective sets. It first finds the roots of both elements using the find operation. If the roots are different, it makes one root point to the other, effectively attaching one tree under the other's root.
def union(x, y):
root_x = find(x)
root_y = find(y)
if root_x != root_y:
parent[root_x] = root_y # naive: always attach x's root to y's rootWithout optimizations, repeated unions can create a degenerate tree of height n, making subsequent find operations linear. This is where the two classic optimizations come into play.
Basic Implementation (Without Optimizations)
Let's start with a complete but unoptimized implementation to understand the baseline before adding improvements:
class DisjointSetNaive:
def __init__(self, n):
"""Initialize n disjoint sets, one for each element 0..n-1."""
self.parent = list(range(n)) # each element is its own parent (root)
def find(self, x):
"""Find the root/representative of the set containing x."""
if self.parent[x] != x:
return self.find(self.parent[x])
return x
def union(self, x, y):
"""Merge the sets containing x and y."""
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y # attach root_x under root_y
return True # union was performed
return False # already in same set
# Example usage
dsu = DisjointSetNaive(10)
dsu.union(1, 2)
dsu.union(2, 3)
dsu.union(4, 5)
print(dsu.find(1)) # might output 3 (depending on union order)
print(dsu.find(2)) # same root as 1
print(dsu.find(4)) # different root from 1, 2, 3
print(dsu.find(1) == dsu.find(3)) # True - same set
print(dsu.find(1) == dsu.find(4)) # False - different setsIn this naive version, the worst-case scenario occurs when we union elements in a specific order. For example, union(0,1), union(1,2), union(2,3)... creates a chain of length n. Finding the root then requires traversing all n nodes — O(n) per operation.
Optimized Implementation: Union by Rank and Path Compression
Two complementary optimizations transform the disjoint set data structure from potentially O(n) per operation to amortized nearly O(1). Together, they achieve a time complexity bounded by the inverse Ackermann function, which for all practical input sizes is effectively constant (≤ 5).
Optimization 1: Union by Rank (or Union by Size)
Union by Rank ensures that when merging two trees, we always attach the shorter tree under the root of the taller tree. This prevents trees from becoming unnecessarily tall. The "rank" of a node is an upper bound on the height of the subtree rooted at that node. Initially all ranks are 0. When merging two trees of equal rank, the resulting root's rank increases by 1.
Alternatively, Union by Size attaches the smaller tree (by number of elements) under the larger tree. Both strategies guarantee that the tree height stays O(log n), giving find operations a logarithmic bound even without path compression.
Optimization 2: Path Compression
Path compression is applied during the find operation. After finding the root, it retroactively points every node along the traversed path directly to the root. This dramatically flattens the tree structure over time. Subsequent find operations on those nodes become essentially instant (one hop).
Path compression does not affect the correctness of the structure — it only changes parent pointers to improve future performance.
Complete Optimized Implementation
Here is the full implementation with both union by rank and path compression:
class DisjointSet:
def __init__(self, n):
"""
Initialize a disjoint set data structure with n elements (0 to n-1).
Each element starts in its own singleton set.
"""
self.parent = list(range(n))
self.rank = [0] * n # tracks approximate tree height
self.size = [1] * n # optional: tracks number of elements per set
self.count = n # number of distinct sets
def find(self, x):
"""
Find the root of the set containing element x.
Applies path compression: flattens the tree by making all nodes
on the path point directly to the root.
Time complexity: O(α(n)) amortized, where α is the inverse Ackermann function.
"""
# Iterative implementation with path compression
root = x
while self.parent[root] != root:
root = self.parent[root] # walk up to find the root
# Path compression: point all nodes on the path directly to the root
while x != root:
next_node = self.parent[x]
self.parent[x] = root
x = next_node
return root
def find_recursive(self, x):
"""
Recursive version of find with path compression.
Elegant and compact, but may hit recursion limits for very deep trees.
"""
if self.parent[x] != x:
self.parent[x] = self.find_recursive(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
Merge the sets containing elements x and y.
Uses union by rank to keep trees balanced.
Returns True if a merge occurred, False if already in the same set.
Time complexity: O(α(n)) amortized.
"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # already in the same set
# Union by rank: attach the tree with lower rank under the higher rank root
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
self.size[root_y] += self.size[root_x]
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
self.size[root_x] += self.size[root_y]
else:
# Ranks are equal: arbitrarily make root_x point to root_y
# and increase root_y's rank by 1
self.parent[root_x] = root_y
self.rank[root_y] += 1
self.size[root_y] += self.size[root_x]
self.count -= 1 # one fewer distinct set
return True
def connected(self, x, y):
"""Check if elements x and y are in the same set."""
return self.find(x) == self.find(y)
def get_size(self, x):
"""Return the size of the set containing element x."""
return self.size[self.find(x)]
def get_count(self):
"""Return the number of disjoint sets."""
return self.count
# Example demonstration
dsu = DisjointSet(10)
# Perform some unions
dsu.union(1, 2)
dsu.union(2, 3)
dsu.union(4, 5)
dsu.union(6, 7)
dsu.union(7, 8)
dsu.union(8, 9)
# Now let's merge two larger sets
dsu.union(3, 9) # merges {1,2,3} with {6,7,8,9}
print(f"Number of sets: {dsu.get_count()}") # 4 sets remaining
print(f"Size of set containing 1: {dsu.get_size(1)}") # 6 (1,2,3,6,7,8,9)
print(f"Are 1 and 9 connected? {dsu.connected(1, 9)}") # True
print(f"Are 1 and 4 connected? {dsu.connected(1, 4)}") # False
# Demonstrate path compression by inspecting parent pointers
print(f"Parent of 2: {dsu.parent[2]}") # likely points to root or near-root
print(f"Root of 2: {dsu.find(2)}") # the representative elementUnion by Size Variant
Sometimes tracking the exact size of each set is more useful than rank, especially when you need to query component sizes frequently. Here's the union-by-size approach:
def union_by_size(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
# Attach the smaller tree under the larger tree
if self.size[root_x] < self.size[root_y]:
self.parent[root_x] = root_y
self.size[root_y] += self.size[root_x]
else:
self.parent[root_y] = root_x
self.size[root_x] += self.size[root_y]
self.count -= 1
return TrueUnion by size guarantees the same logarithmic height bound as union by rank. The choice between them depends on whether you need accurate size information (use size) or prefer slightly simpler logic without needing to update rank on equal merges (rank is conceptually simpler but size is more informative).
Time Complexity Analysis
The time complexity of disjoint set operations is one of the most fascinating results in algorithm analysis. Let's build up the understanding step by step.
Naive Implementation
Without any optimizations, both find and union are O(n) in the worst case. Consider this pathological sequence:
dsu = DisjointSetNaive(1000)
for i in range(999):
dsu.union(i, i+1) # creates a chain of 1000 nodes
dsu.find(0) # traverses all 999 parent pointersEach find on element 0 must walk up through all 999 intermediate nodes. With m operations on n elements, the worst-case total time is O(m × n).
Union by Rank Alone
With only union by rank (no path compression), we can prove that the height of any tree is bounded by O(log n). The proof is by induction: a tree of height h must contain at least 2h nodes. Therefore, h ≤ log₂ n. Each find operation takes O(log n) time. The total time for m operations is O(m log n).
Path Compression Alone
With only path compression (naive union), the amortized time per operation is O(log n) as well, but the analysis is more subtle. Over a sequence of operations, path compression progressively flattens trees, yielding an amortized logarithmic bound.
Both Optimizations: The Inverse Ackermann Bound
When both union by rank and path compression are used together, the amortized time per operation becomes:
O(α(n))
where α(n) is the inverse Ackermann function. This function grows so slowly that for any value of n that can fit in the observable universe, α(n) ≤ 5. In practice, this means each operation is effectively constant time.
Understanding the Inverse Ackermann Function
The Ackermann function A(k, n) is defined as:
A(0, n) = n + 1
A(k, 0) = A(k-1, 1) for k > 0
A(k, n) = A(k-1, A(k, n-1)) for k > 0 and n > 0This function grows at a mind-boggling rate. A(1, n) = 2n, A(2, n) = 2n, A(3, n) = 222...n times (a tower of powers), and A(4, n) is incomprehensibly large.
The inverse Ackermann function α(n) is essentially: "what is the smallest k such that A(k, k) ≥ n?" Even for n = 1080 (estimated number of atoms in the universe), α(n) = 4. For any practical computer science problem, α(n) ≤ 5.
Amortized Analysis Sketch
The proof that disjoint set operations run in O(α(n)) amortized time is a landmark result by Tarjan (1975). The key insight is to assign "potential" to nodes based on their rank and track how path compression reduces this potential over time. The analysis uses a hierarchy of "levels" and "steps" defined using the Ackermann function to categorize nodes by how far they are from being fully compressed. Each operation's cost can be charged against a decrease in potential, yielding the inverse Ackermann bound.
Practical Performance Comparison
Here's a benchmark comparing the three variants:
import time
import random
def benchmark():
n = 100000
operations = 500000
# Generate random operations
pairs = [(random.randint(0, n-1), random.randint(0, n-1)) for _ in range(operations)]
# Test naive implementation
dsu_naive = DisjointSetNaive(n)
start = time.time()
for a, b in pairs:
dsu_naive.union(a, b)
for a, b in pairs[:10000]:
dsu_naive.find(a)
naive_time = time.time() - start
print(f"Naive: {naive_time:.4f}s")
# Test optimized implementation
dsu_opt = DisjointSet(n)
start = time.time()
for a, b in pairs:
dsu_opt.union(a, b)
for a, b in pairs[:10000]:
dsu_opt.find(a)
opt_time = time.time() - start
print(f"Optimized: {opt_time:.4f}s")
print(f"Speedup: {naive_time / opt_time:.1f}x")
# Typical output:
# Naive: 2.8473s
# Optimized: 0.3121s
# Speedup: 9.1xThe optimized version is dramatically faster, and the gap widens as n grows. For very large inputs, the naive version can become completely unusable.
Advanced Variants and Techniques
Iterative Find with Two-Pass Path Compression
The iterative find implementation shown earlier uses two passes: one to find the root and another to compress the path. This is efficient and avoids recursion depth issues. Here's a more compact one-pass variant that compresses as it goes:
def find_two_pass(self, x):
# First pass: find the root
root = x
while self.parent[root] != root:
root = self.parent[root]
# Second pass: compress the path
while x != root:
parent_x = self.parent[x]
self.parent[x] = root
x = parent_x
return rootRecursive Find with Implicit Path Compression
The recursive version is elegant and commonly used in competitive programming due to its brevity:
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]This recursively finds the root and on the way back up, sets each node's parent to the root. It's effectively a one-pass compression. The only caution is that Python's default recursion limit (typically 1000) might be exceeded for very deep unoptimized trees. However, with union by rank, tree depths stay small enough that this is rarely an issue.
Disjoint Set with Explicit Deletion (Time Travel)
Standard disjoint set does not support removing an element from a set or "undoing" a union. However, a variant using persistent data structures or maintaining an undo stack can support rollback of recent operations:
class DisjointSetWithUndo:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.history = [] # stack of (node, old_parent, old_rank) tuples
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
# Record state for potential undo
self.history.append((root_y, self.parent[root_y], self.rank[root_x]))
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
return True
def undo(self):
"""Undo the most recent union operation."""
if not self.history:
return False
node, old_parent, old_rank = self.history.pop()
root_x = self.parent[node] # the root that absorbed node
self.parent[node] = old_parent
if old_rank is not None:
self.rank[root_x] = old_rank
return TrueThis pattern is useful in algorithms that need to backtrack, such as certain dynamic connectivity problems or branch-and-bound search with incremental constraints.
Practical Applications with Code Examples
Application 1: Kruskal's Algorithm for Minimum Spanning Tree
Kruskal's algorithm finds the minimum spanning tree of a graph by processing edges in increasing weight order, using disjoint sets to avoid cycles:
def kruskal_mst(vertices, edges):
"""
vertices: number of vertices (0 to vertices-1)
edges: list of (weight, u, v) tuples
returns: list of edges in the MST, total weight
"""
dsu = DisjointSet(vertices)
edges.sort(key=lambda e: e[0]) # sort by weight
mst = []
total_weight = 0
for weight, u, v in edges:
if dsu.union(u, v): # if u and v were in different sets
mst.append((u, v, weight))
total_weight += weight
if len(mst) == vertices - 1:
break # MST is complete
return mst, total_weight
# Example graph with 6 vertices
edges = [
(1, 0, 1), (2, 0, 2), (3, 1, 2), (4, 0, 3),
(5, 2, 3), (6, 3, 4), (7, 2, 4), (8, 4, 5),
(9, 3, 5)
]
mst, weight = kruskal_mst(6, edges)
print(f"MST edges: {mst}")
print(f"Total weight: {weight}")Application 2: Connected Components in an Undirected Graph
Finding all connected components in a graph is straightforward with disjoint sets:
def connected_components(n, edges):
"""
n: number of vertices
edges: list of (u, v) pairs
returns: list of sets, each representing a connected component
"""
dsu = DisjointSet(n)
# Union all connected vertices
for u, v in edges:
dsu.union(u, v)
# Group vertices by their root
components = {}
for v in range(n):
root = dsu.find(v)
if root not in components:
components[root] = set()
components[root].add(v)
return list(components.values())
# Example: graph with two disconnected components
edges = [(0,1), (1,2), (3,4), (4,5), (3,5)]
components = connected_components(6, edges)
print(f"Components: {components}")
# Output: Components: [{0, 1, 2}, {3, 4, 5}]Application 3: Cycle Detection
Detecting cycles in an undirected graph as edges are added:
def has_cycle(n, edges):
"""
Returns True if the graph contains a cycle.
Assumes edges are processed in the given order.
"""
dsu = DisjointSet(n)
for u, v in edges:
if not dsu.union(u, v):
# u and v already in the same set → adding edge creates a cycle
return True
return False
# Example: graph with a cycle
edges_with_cycle = [(0,1), (1,2), (2,3), (3,0)]
print(f"Has cycle: {has_cycle(4, edges_with_cycle)}") # True
edges_without_cycle = [(0,1), (1,2), (2,3)]
print(f"Has cycle: {has_cycle(4, edges_without_cycle)}") # FalseApplication 4: Percolation (Union-Find on a Grid)
The percolation problem models whether a system of open cells allows flow from top to bottom. Disjoint sets elegantly solve this:
class Percolation:
def __init__(self, n):
"""
n x n grid. Cells are indexed 0 to n*n-1.
Virtual top node (n*n) connects to all top-row open cells.
Virtual bottom node (n*n+1) connects to all bottom-row open cells.
"""
self.n = n
self.size = n * n
self.virtual_top = self.size
self.virtual_bottom = self.size + 1
self.dsu = DisjointSet(self.size + 2) # +2 for virtual nodes
self.open_cells = set()
# Connect virtual top to top row initially? No, only when cells open.
def open(self, row, col):
"""Open a cell at (row, col) and connect to adjacent open cells."""
index = row * self.n + col
if index in self.open_cells:
return
self.open_cells.add(index)
# Connect to virtual top if in top row
if row == 0:
self.dsu.union(index, self.virtual_top)
# Connect to virtual bottom if in bottom row
if row == self.n - 1:
self.dsu.union(index, self.virtual_bottom)
# Connect to adjacent open cells (up, down, left, right)
for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
r, c = row + dr, col + dc
if 0 <= r < self.n and 0 <= c < self.n:
neighbor_index = r * self.n + c
if neighbor_index in self.open_cells:
self.dsu.union(index, neighbor_index)
def percolates(self):
"""Check if any top-row open cell is connected to any bottom-row open cell."""
return self.dsu.connected(self.virtual_top, self.virtual_bottom)
# Example: 3x3 grid
perc = Percolation(3)
perc.open(0, 1) # top row, middle
perc.open(1, 1) # middle row, middle
perc.open(2, 1) # bottom row, middle
print(f"Percolates: {perc.percolates()}") # True - vertical path existsBest Practices and Common Pitfalls
1. Always Use Both Optimizations
Never deploy a disjoint set without both union by rank (or size) and path compression. The naive version is unacceptably slow for any non-trivial input. The two optimizations together give you the near-constant amortized time guarantee.
2. Prefer Iterative Find for Deep Trees
While the recursive find is elegant, it can hit Python's recursion limit if used without union by rank or on pre-existing deep trees. The iterative two-pass version is safer in production code. If you use recursion, set sys.setrecursionlimit() appropriately or guarantee union by rank is always in place.
3. Use 0-Based Indexing Internally
Map your domain elements to contiguous integers 0 through n-1 for efficient array-based storage. If your elements are strings, objects, or non-contiguous IDs, use a dictionary to map them to integer indices first.
class DisjointSetMapped:
def __init__(self, elements):
self.map = {elem: i for i, elem in enumerate(elements)}
self.dsu = DisjointSet(len(elements))
def union(self, a, b):
return self.dsu.union(self.map[a], self.map[b])
def find(self, a):
root_idx = self.dsu.find(self.map[a])
# Reverse lookup to return the original element
for elem, idx in self.map.items():
if idx == root_idx:
return elem4. Track Set Sizes When Needed
If your application needs to query the size of sets frequently, maintain a size array and update it during unions. This avoids O(n) traversals to count elements. The size array also serves the same balancing purpose as rank.
5. Reset Parent Pointers Carefully
If you need to reuse a disjoint set structure (e.g., in a loop processing different graphs), reset both the parent and rank/size arrays. Simply resetting parent pointers to self-pointers while keeping stale rank values will break the union-by-rank guarantees.
6. Beware of Amortized Guarantees
The O(α(n)) bound is amortized across a sequence of operations. Any single operation could theoretically take O(log n) time (though with path compression this becomes vanishingly unlikely). For real-time systems with strict per-operation deadlines, consider the worst-case O(log n) bound with union by rank alone.
7. Thread Safety
The standard disjoint set is not thread-safe. Concurrent find operations can interfere with path compression (one thread might read a stale parent while another is updating it). For multi-threaded use, either synchronize all operations with locks or use a concurrent variant with atomic operations.
8. Use the Right Data Structure for the Problem
Disjoint sets excel at dynamic connectivity (adding edges incrementally). For static graphs where all edges are known upfront, BFS/DFS might be simpler and equally efficient. For problems requiring both additions and deletions of edges, you need more sophisticated data structures like dynamic connectivity trees (link-cut trees, Euler tour trees).
Conclusion
The disjoint set data structure stands as one of the most elegant and powerful tools in algorithm design. Its conceptual simplicity — a forest of trees with two basic operations — belies the sophisticated mathematical analysis that guarantees near-constant time performance. By combining union by rank and path compression, we achieve an amortized time complexity of O(α(n)), where the inverse Ackermann function α(n) is effectively constant for all practical purposes.
This data structure is not merely a theoretical curiosity; it underpins critical algorithms in graph theory (Kruskal's MST), network analysis (connected components, cycle detection), and physical simulations (percolation). Understanding its implementation details — from the two-pass iterative find to the subtle rank updates during union — equips developers to deploy it confidently and correctly.
When implementing disjoint sets in your own projects, remember the key best practices: always use both optimizations, prefer iterative find for robustness, map domain elements to contiguous integers, and be mindful of the amortized nature of the performance guarantees. With these principles in mind, you can harness the full power of this remarkable data structure to solve connectivity problems with unparalleled efficiency.