Union-find, also called a disjoint-set union (DSU), is a data structure that keeps a collection of elements divided into groups, with every element in exactly one group. It has two operations: find tells which group an element is in, and union merges two groups into one. Groups are never split. The structure suits a graph that receives its edges one at a time, where the groups are the connected components and each new edge may merge two of them.
Each group as a tree
Union-find stores each group as a tree. One element of the group is the root of the tree. Every other element has a link to another element of the group, its parent, and following the links from any element leads to the root. The links are kept in an array: parent[v] is the parent of , and for a root, which has no element above it, parent[v] is itself. The root stands for the whole group and is also called its representative.
The walk along the links is the operation find: find(v) starts at , follows the links until it reaches an element that is its own parent, and returns that root. Two elements are in the same group exactly when find returns the same root for both. The operation union merges two groups: union(a, b) finds the roots of and and, if they are different, makes one of them the parent of the other, which hangs one whole tree under the other root.
[0, 0, 0, 2, 4, 5] drawn as three trees. Each arrow points from to parent[v], and find(3) follows the highlighted arrows to the root 0.find(3) goes from 3 to its parent 2 and from 2 to 0, which is its own parent, so it returns 0. find(1) returns 0 as well, so 1 and 3 are in the same group, although neither is the parent of the other. Elements 4 and 5 are roots without children, and each is a group of its own.