Interactive Lab · DSA & Algorithms
Friend networks, Kruskal's minimum spanning tree, "is the maze solved yet", detecting a cycle as edges arrive, they're all the same question: are two elements in the same group? Union-find (a disjoint-set structure) answers it with two tiny operations: find(x) tells you which set x belongs to, and union(a, b) merges the two sets. Start with every element alone, stream edges in one at a time, and watch the groups fuse, and watch an edge that connects two already-joined elements get flagged as a cycle. Scrub the unions.
🎬 Watch the 70-second explainer, then merge the sets yourself below ↓
▶ The playground, add edges one at a time; each colour is one disjoint set
Ten elements start in ten sets of one. Each union draws an edge and, if the two ends were in different sets, merges them (they take one colour). If they were already in the same set, the edge is redundant, a dashed red cycleand nothing merges.
Union-Find detects connectivity at near-O(1): Kruskal's MST (network cabling, clustering), cycle detection in dependency graphs, image-region labeling, account-deduplication in identity systems, and percolation physics. The non-merge-means-cycle signal you just caught is exactly how redundant edges are rejected at scale.
The code that's actually running, two tricks make it almost free
Keep an eye on the disjoint sets counter: it starts at 10 and drops by one on every real merge. Predict where it stalls. At edge 5, union(1, 3), the counter doesn't move, because 1 and 3 are already in the same set (find(1) == find(3)). That non-merge is a cycle, and catching it is exactly how you detect a cycle in a graph, or reject a redundant edge while building Kruskal's MSTin almost O(1). Why does find stay fast even when a set has millions of elements? (Two ideas: path compression and union by rank.)
The takeaway
find(x) returns the representative of x's set; union(a, b) links two sets into one. Streaming edges through them tracks connectivity as it changes.find(a) == find(b) before you union, the two are already connected, the new edge closes a loop. That single check powers cycle detection and Kruskal's MST (skip any edge that would form a cycle).find re-points the nodes it walks straight at the root, flattening the tree, so the next lookup is nearly instant.α(n) (inverse Ackermann) per op, ≤ 4 for any n you'll ever see. You watched ten sets fuse into one and a redundant edge get caught as a cycle.