Union-Find (Disjoint Set)
Track connected components in near-constant time with path compression and union by rank.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Two arrays, huge power
Union-Find (also called Disjoint Set Union, DSU) tracks a collection of disjoint sets under two operations: find(x) returns a representative of x's set, and union(a, b) merges the sets containing a and b. All you need are two integer arrays — parent and rank.
Path compression
Every time find walks up to the root, flatten the tree by pointing intermediate nodes directly at the root. Subsequent finds on those elements are O(1). The one-line trick parent[x] = parent[parent[x]] (path halving) is a lighter variant that's nearly as effective and easier to write correctly.
Union by rank
When merging two trees, attach the shorter one under the taller one. That keeps the trees shallow. Rank is an upper bound on tree height; it only increases when two equal-rank trees are merged. Combined with path compression, this pushes every operation to O(α(n)) — the inverse Ackermann function, which is at most 4 for any n that fits in the universe.
Kruskal's minimum spanning tree
Sort edges by weight, then walk through them: for each edge (a, b), if union(a, b) returns true (they weren't already connected) include the edge in the MST. Stop when you've added n-1 edges. Union-Find makes the connectivity check trivial.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Other applications
Cycle detection in undirected graphs, dynamic connectivity as edges arrive over time, percolation problems, image segmentation, and offline range queries (with a sweep line). Whenever you're asking 'are these two things in the same group yet?', reach for Union-Find.
Limitations
Union-Find supports merge but not split. If you need to remove edges over time, you need a heavier structure (link-cut trees, or offline processing that runs history in reverse). It also doesn't track set size unless you maintain a size[] array alongside — a common extension.
Related lessons & next topics
Keep going — these pair well with Union-Find (Disjoint Set).
- § 6.01 · Data Structures in JavaArrays and ArrayList — the workhorses
Fixed-size arrays vs dynamic ArrayList. Memory layout, amortized O(1) append, and when each one shines.
Beginner · 22 min - § 6.02 · Data Structures in JavaLinkedList and the Deque interface
Doubly-linked nodes, O(1) insert at either end, and why LinkedList is almost never the right choice.
Beginner · 20 min - § 6.03 · Data Structures in JavaStacks, queues, and ArrayDeque
LIFO, FIFO, and why java.util.Stack is a historical mistake you should avoid.
Intermediate · 24 min - § 6.04 · Data Structures in JavaHashMap, equals, and hashCode
How hashing works, why you must override equals and hashCode together, and the load factor that keeps lookups O(1).
Intermediate · 28 min