04
Union-Find Visualizer
Chapter 4 • Intermediate
90 min
Union-Find Visualizer
What is Union-Find?
Union-Find (Disjoint Set Union) is a data structure that efficiently:
- Find: Determine which set an element belongs to
- Union: Merge two sets
Operations
- make_set(x): Create new set containing x
- find(x): Find representative of set containing x
- union(x, y): Merge sets containing x and y
Naive Implementation
python.js
class UnionFindNaive:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
return self.find(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:
self.parent[root_y] = root_x
Time Complexity: O(n) per operation (worst case)
Optimized Implementation
Path Compression
Make all nodes point directly to root during find.
python.js
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
Union by Rank
Always attach smaller tree under larger tree.
python.js
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already in same set
# Union by rank
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
Time Complexity
With both optimizations:
- Find: O(α(n)) amortized (inverse Ackermann function, effectively constant)
- Union: O(α(n)) amortized
Applications
- Kruskal's algorithm: Cycle detection
- Connected components: Find all components
- Network connectivity: Check if nodes connected
- Image processing: Connected component labeling
- Equivalence relations: Group equivalent elements
Example: Connected Components
python.js
def connected_components(n, edges):
"""Find number of connected components"""
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
# Count distinct roots
roots = set()
for i in range(n):
roots.add(uf.find(i))
return len(roots)
Practice Problems
- Implement Union-Find with optimizations
- Count connected components
- Detect cycle in undirected graph
- Number of islands
- Friend circles
- Redundant connections