Union-Find (Disjoint Set Union)
A data structure that tracks a set of elements partitioned into disjoint (non-overlapping) subsets. Also known as Disjoint Set Union (DSU), it provides near-constant time operations for union (merging sets) and find (determining which set an element belongs to). With path compression and union by rank optimizations, operations run in O(α(n)) amortized time, where α is the inverse Ackermann function, effectively constant for all practical purposes.
Visualization
Interactive visualization for Union-Find (Disjoint Set Union)
Union-Find (Disjoint Set Union)
Union Operation
Find Operation
• Union: O(α(n)) - Merges two sets with union by rank
• Find: O(α(n)) - Finds root with path compression
• α(n) is inverse Ackermann function (effectively constant)
Interactive visualization with step-by-step execution
Implementation
1class UnionFind {
2 private parent: number[];
3 private rank: number[];
4 private count: number;
5
6 constructor(n: number) {
7 this.parent = Array.from({length: n}, (_, i) => i);
8 this.rank = Array(n).fill(0);
9 this.count = n;
10 }
11
12 find(x: number): number {
13 if (this.parent[x] !== x) {
14 // Path compression: make x point directly to root
15 this.parent[x] = this.find(this.parent[x]);
16 }
17 return this.parent[x];
18 }
19
20 union(x: number, y: number): boolean {
21 const rootX = this.find(x);
22 const rootY = this.find(y);
23
24 if (rootX === rootY) return false; // Already in same set
25
26 // Union by rank: attach smaller tree under larger tree
27 if (this.rank[rootX] < this.rank[rootY]) {
28 this.parent[rootX] = rootY;
29 } else if (this.rank[rootX] > this.rank[rootY]) {
30 this.parent[rootY] = rootX;
31 } else {
32 this.parent[rootY] = rootX;
33 this.rank[rootX]++;
34 }
35
36 this.count--;
37 return true;
38 }
39
40 connected(x: number, y: number): boolean {
41 return this.find(x) === this.find(y);
42 }
43
44 getCount(): number {
45 return this.count;
46 }
47}
48
49// Union by Size variant
50class UnionFindSize {
51 private parent: number[];
52 private size: number[];
53
54 constructor(n: number) {
55 this.parent = Array.from({length: n}, (_, i) => i);
56 this.size = Array(n).fill(1);
57 }
58
59 find(x: number): number {
60 if (this.parent[x] !== x) {
61 this.parent[x] = this.find(this.parent[x]);
62 }
63 return this.parent[x];
64 }
65
66 union(x: number, y: number): boolean {
67 const rootX = this.find(x);
68 const rootY = this.find(y);
69
70 if (rootX === rootY) return false;
71
72 // Union by size
73 if (this.size[rootX] < this.size[rootY]) {
74 this.parent[rootX] = rootY;
75 this.size[rootY] += this.size[rootX];
76 } else {
77 this.parent[rootY] = rootX;
78 this.size[rootX] += this.size[rootY];
79 }
80
81 return true;
82 }
83}Deep Dive
Theoretical Foundation
Union-Find (Disjoint Set Union) maintains a forest of trees where each tree represents a disjoint set. Each element points to its parent, with the root representing the set. The data structure supports two operations: Find (determine which set an element belongs to) and Union (merge two sets). Without optimizations, operations are O(n), but with path compression and union by rank, amortized time is O(α(n)) where α is the inverse Ackermann function, effectively constant. Path compression flattens tree during find by making all nodes on path point directly to root. Union by rank/size attaches smaller tree under root of larger tree, keeping trees shallow.
Complexity
Time
O(α(n)) amortized
O(α(n)) amortized
O(α(n)) amortized
Space
O(n)
Applications
Industry Use
Kruskal's Minimum Spanning Tree algorithm
Detecting cycles in undirected graphs
Image segmentation (connected components)
Network connectivity
Least Common Ancestor (LCA) problems
Percolation theory simulations
Social network friend groups
Equivalence class problems
Use Cases
Related Algorithms
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.
Merge Sort
A stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) performance.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire array is sorted. Named for the way larger elements 'bubble' to the top (end) of the array.
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how people sort playing cards in their hands - picking each card and inserting it into its correct position among the already sorted cards. Despite its O(n²) time complexity, Insertion Sort is efficient for small datasets and nearly sorted arrays, making it practical for real-world applications.