Introduction to Union Find

The union find pattern is used to group elements into sets based on a specified property. Each set is nonoverlapping, that is, it contains unique elements that are not present in any other set. The pattern uses a disjoint set data structure, such as an array, to keep track of which set each element belongs to.

Each set forms a tree data structure and has a representative element that resides at the root of the tree. Every element in this tree maintains a pointer to its parent. The representative’s parent pointer points to itself. If we pick any element in a set and follow its parent pointers, we’ll always reach the set representative.

The pattern is composed of two operations performed on the disjoint data structure:

• find(v): Finds the representative of the set that contains v.

• union(v1, v2): Merges the sets containing v1 and v2 into one.

Here is how the union find pattern uses these operations to form and extract information from sets of elements:

Note: In the above illustration, we skipped the union(3,4) function to demonstrate how trees of heights greater than $1$ can be merged.

For now, the worst-case time complexity of this approach is $O(n)$ because we might have to traverse the entire tree to find the representative of an element.

We can improve the ...