Union-Find (Disjoint Sets)
Medium+90 XPA tiny structure that answers 'are these two things connected?' almost instantly — the heart of network and MST algorithms.
No visualization loaded.
Watch
—
Press Run to begin.
Union-Find keeps track of GROUPS. Imagine islands joined by bridges: at any moment you want to ask 'can I get from island A to island B?' Each element points at a parent; follow the parents upward and you reach a 'root.' Two elements are in the same group exactly when they reach the SAME root. To MERGE two groups (union), you find both roots and hang one under the other. To CHECK a group (find), you walk up to the root. With two cheap tricks it becomes so fast it's basically free.
▸What problem does it actually solve?
'Are these two things connected?' — over and over, as connections keep being added. Friends-of-friends in a social network, computers on the same network, cells in the same blob of an image, towns joined by roads. You don't need the whole path between them; you just need to know they end up in the same group. Union-Find answers that in almost constant time.
▸What is 'union'?
Merging two groups into one. You find the root of each element, and if the roots are different you point one root at the other — now everyone in both groups reaches the same root, so they're one group. If the roots are already the same, they were connected already and there's nothing to do.
▸What is 'find'?
Discovering WHICH group an element is in by walking parent pointers up to the root. The root is the group's name. Two finds that return the same root mean the two elements are connected. find is how every other operation decides which set an element belongs to.
▸What are path compression and union by rank?
Two speed tricks that keep the trees almost flat. Union by RANK always hangs the SHORTER tree under the taller one, so merging never makes a tall, slow chain. Path COMPRESSION: after a find walks up to the root, it re-points every node it passed straight at the root — so the next find is a single hop. Together they make each operation nearly O(1).
▸Where is it used?
Kruskal's algorithm for minimum spanning trees (add an edge only if its two endpoints aren't already connected — a union-find check), detecting cycles in a graph, network/connectivity queries, image segmentation (flood-fill blobs), and account/percolation problems. Anywhere you keep merging groups and asking 'same group?', this is the tool.
How the work grows
~O(1) amortized (inverse Ackermann α(n)) is instant — doesn't grow at all. With union by rank and path compression the trees stay so flat that each find or union costs an almost-constant amount of work — formally the inverse Ackermann function α(n), which is below 5 for any number of elements you could ever store. Space is just one parent slot (plus a tiny rank) per element.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.