Data structures and algorithms 0/7

DSA, Graphs

What is union-find (disjoint set union)?

Also called disjoint set union, DSU, disjoint-set data structure

340 words · 2 min read

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 vv, and for a root, which has no element above it, parent[v] is vv 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 vv, 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 aa and bb and, if they are different, makes one of them the parent of the other, which hangs one whole tree under the other root.

The array [0, 0, 0, 2, 4, 5] drawn as three trees. Each arrow points from vv 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.

Union-find (DSU): merging disjoint sets Track connected groups as edges arrive, keep the trees short with union by size and path compression, and build minimum spanning trees with Kruskal and Prim. Read the full lesson