Union-Find: Tracking Which Items Share a Group

Union-find, also called a disjoint-set structure, keeps track of which items belong to the same group while groups are merged. This card covers how it stores every group in one array of parents, how find follows that array to a group's representative, how union merges two whole groups with one assignment, and what the operations cost before any optimisation.

The items are numbered 0 to n - 1, and parent[x] holds another item, or x itself. Following parents from any item always ends at an item that is its own parent, called the root, and the root is the group's representative. Each group is therefore a tree, a structure in which every item but one has a single parent, and the whole array is a forest, a collection of such trees.

Two operations work on it:

• find(x) follows parents from x until it reaches the root, and returns that root. Two items are in the same group when find returns the same root for both.
• union(a, b) finds the root of a and the root of b and, when they differ, sets the parent of a's root to b's root.

Think of clubs in which every member knows one person to ask about club business, and the chain of asking ends at the club's president. Two people belong to the same club when their chains end at the same president, and two clubs merge when one president starts asking the other. The analogy breaks there: merging two real clubs takes a vote and a reorganisation, and union is one assignment.

A run started six items, 0 to 5, each its own root, then performed union(0, 1), union(1, 2) and union(3, 4). The diagram draws the result, each arrow pointing from an item to its parent.

The table lists this forest as the array the code stores.

Items 2, 4 and 5 are their own parents, so there are three groups: {0, 1, 2} with root 2, {3, 4} with root 4, and {5} on its own. find(0) follows 0, 1, 2 and returns 2, so 0 and 2 share a group; find(3) returns 4, so 0 and 3 do not. The run printed exactly these answers.

Nothing stops a tree from growing into a long chain, so find, and union, which calls it twice, can follow up to n - 1 parents. Two optimisations, union by rank and path compression, keep the trees flat. The table gives the cost without and with them, where amortised means averaged over a long sequence of operations and α(n) is a function that grows so slowly it is at most 4 for any n that fits in memory.