Union-Find

Union-find (also called a disjoint set) tracks which group each element belongs to, under two operations: find (who is this element's group representative, or "root"?) and union (merge two groups). This animation draws elements as floating bubbles tinted by group, each with a parent arrow — the arrows form small trees, and each tree's root represents the group.

On union, the two elements' roots are found first; then one root arcs over and docks under the other, and the merged group flash-fills one color. On find, watch the walk up the parent chain to the root — then path compression fires: every visited bubble snaps its arrow to point directly at the root, flattening the tree so the next find is a single hop.

What to watch for:

• Unions happen between roots, not the bubbles you clicked. Merging non-roots would corrupt the trees.
• Compression is where the speed lives. Without it, chains grow long and finds crawl; with it (plus docking the shorter tree under the taller), trees stay so flat that operations are effectively constant time.
• The cycle signal. Union two bubbles that already share a root and nothing merges — that "already connected" no-op is exactly how union-find detects a redundant, cycle-creating edge.