Union Find: Introduction

Let’s go over the Union Find pattern, its real-world applications and some problems we can solve with it.

We'll cover the following

About the pattern

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: