Lesson 20 — Union-Find

Union-Find: who is in the same group?

Union-Find (also called disjoint-set) tracks groups that merge over time. Every item points to a parent; the item at the top of the chain (whose parent is itself) is the group's root. find(x) climbs to the root. union(a, b) joins two groups by pointing one root at the other. Two items are connected if they have the same root.

parent = [0, 0, 2]   # 1 points to 0; 0 and 2 are roots

Why it matters: it answers "are these connected?" almost instantly — used for network connectivity, image regions and Kruskal's minimum spanning tree.