Union-Find (disjoint set union) tracks which elements are in the same group. union(a, b) merges two groups; find(a) returns a group's representative; connected(a, b) is just find(a) === find(b). Two optimizations — union by size and path compression — make every operation effectively O(1). Each colour is one set.
Every element in its own set. Union two to merge their trees.
elements (n)
12
disjoint sets
12
largest set
1
operations
0
Try this:union a few pairs and watch separate trees merge into one coloured set — union by size always hangs the smaller tree under the larger root, so trees stay shallow. Then pick a deep node and hit find(x) + compress: it walks up to the root (amber path), then path compression re-points every node on that path straight to the root — flattening the tree so the next find is instant. connected(a, b) never needs the path itself, just whether the two roots match. Together these give α(n) (inverse-Ackermann — basically constant) amortized time, which is why union-find powers Kruskal's MST, cycle detection, connected components, and network connectivity.