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.