Union-Find

Union-find is the data structure that tracks which items belong to the same group while groups are merged, storing every group as a tree in one array of parents. It matters because it answers "are these two connected?" in close to constant time, which is what counting the separate parts of a network or finding the edge that closes a cycle needs. The topic starts with the parent array and the two operations, find and union, then traces four unions by hand and reads the groups back. It shows what goes wrong when union links the items it was given instead of their roots, explains how union by rank and path compression keep the trees flat and why both are needed, and implements the structure in three languages. It ends with an exercise on the computer networks in a building.