Intuition First: Who's in My Friend Group?#
At a big party, people drift into clusters. If Aisha knows Ben, and Ben knows Carlos, then all three belong to one social circle, even if Aisha and Carlos have never actually met. Now two questions come up constantly: "are these two people already in the same group?" and "these two groups just merged, so treat them as one from now on."
That's precisely what Union-Find does, and it answers both in nearly constant time. find tells you which group an element is in; union fuses two groups together. This simple pair of operations is behind network-connectivity checks, friend suggestions, image segmentation, and cycle detection in graphs.