Union-Find, step by step.

Union-find, also called a disjoint-set data structure or DSU, keeps elements in sets that never overlap: find tells which set holds an element, and union merges two sets. With union by rank and path compression, both take almost constant time. This page explains how it works, with step-by-step animations of union by rank and path compression from the VisiGrab app.

How union-find works

What is union-find (disjoint set union, DSU)?

Union-find, also called a disjoint-set data structure, disjoint set union (DSU) or merge-find set, keeps elements in sets that never overlap. It answers two questions in almost constant time: which set holds an element, and whether two elements are in the same set. Find names an element's set, and union merges two sets into one.

Bernard Galler and Michael Fischer described its forest of parent links in 1964, and Robert Tarjan proved its near-constant cost in 1975.

The disjoint-set forest: parent links and the root

Each set is a tree, and the trees together form a forest. Every node keeps one link, to its parent. The root is the node that is its own parent: the set's representative. Two elements share a set exactly when they share a root. In code, each element number indexes its parent and its rank: for a root, its rank is a bound on its tree's height.

The app draws element 0 as A, 1 as B and so on, leaves out each root's link to itself, and writes the rank above each root.

How does union-find work? Find, union and path compression

1. Make-set: each element starts as its own parent with rank 0, a set of one.

2. Find: from the element, follow parent links upwards until a node is its own parent. That root is the answer.

3. Path compression: once the root is known, link every node on the walked path straight to it, so the next find from any of them takes one step.

4. Union: find the roots of both elements. If they are the same, the elements already share a set and the union stops. Otherwise one root becomes the child of the other: the link itself changes only that root's parent, and every node below it keeps its parent.

5. Union by rank: the root of higher rank becomes the parent, and its rank stays. When the ranks are equal, the first element's root becomes the parent and its rank goes up by one. Only a union changes a rank, and only on a tie.

Union-find pseudocode: find with path compression, union by rank

The app's code is a class UnionFind whose constructor makes every element a set of its own. In pseudocode:

UnionFind(count)
    for i from 0 to count - 1
        parent[i] = i
        rank[i] = 0

find(element)
    if parent[element] != element
        root = find(parent[element])
        parent[element] = root
    return parent[element]

union(x, y)
    xRoot = find(x)
    yRoot = find(y)
    if xRoot == yRoot
        return
    if rank[xRoot] < rank[yRoot]
        parent[xRoot] = yRoot
    else if rank[xRoot] > rank[yRoot]
        parent[yRoot] = xRoot
    else
        parent[yRoot] = xRoot
        rank[xRoot] = rank[xRoot] + 1

find calls itself up the path until parent[element] == element, the root. As the calls return, each node on the path gets root as its parent, the node nearest the root first; a node whose parent is already the root stays as it is. union finds both roots, which compresses both paths, and returns if they match. On a tie the last branch keeps xRoot, the first element's root, on top; the textbook Introduction to Algorithms (CLRS) breaks the tie the other way, and both are correct.

Union by rank example: equal and different ranks

The first player merges the sets of A and C, two trees of rank 1: A over B, and C over D. The ranks tie, so A becomes the parent and its rank rises to 2. Only C gets a new parent: D stays under C, and C's rank is no longer shown, as only a root's rank counts.

Union A and C: equal ranks

All steps as text
  1. Two nodes, A and C, are ready for union.
  2. Both selected nodes are roots.
  3. Since both roots had the same rank before this union operation, and nodes are pre-selected in this example, the predefined logic is applied: the root from the left set becomes the parent, forming a single set.
  4. A is now the root of one set, A, B, C and D, and its rank has grown from 1 to 2.
Union-Find — Union A and C: equal ranks. Last step: A is now the root of one set, A, B, C and D, and its rank has grown from 1 to 2.

The second player starts from that tree, A of rank 2, beside F's tree of rank 1, F over G. F goes under A, and A keeps rank 2. G ends two levels below A, as deep as D, so the tree grows no taller.

Union A and F: different ranks

All steps as text
  1. Two nodes, A and F, are ready for union.
  2. Both selected nodes are roots.
  3. The root with a higher rank becomes the parent, forming a single set.
  4. F's tree now hangs under A, whose rank stays 2: the tree is no taller than before.
Union-Find — Union A and F: different ranks. Last step: F's tree now hangs under A, whose rank stays 2: the tree is no taller than before.

A root reaches rank k only when two trees of rank k − 1 merge, so its tree holds at least 2k nodes. With n elements no rank exceeds log2 n, so no find walks more than log2 n links.

Union by size vs union by rank

Union by size, also called weighted quick-union, stores each root's node count instead and hangs the smaller tree under the larger. It gives the same height bound and the same cost with path compression. Choose it when a problem needs the size of each set; otherwise either works.

Path compression example: Find I

Instead of Union A and F, three other unions on the second player's starting forest, with J and K as two extra single-node sets, give A a tree of rank 3: H and I, F and H, then D and F; the last one's find has already linked D straight to A. Find I links H and I straight to A, while F, already under A, stays where it is. The tree's height drops from 3 to 2, but A's rank stays 3.

Find I with path compression

All steps as text
  1. This example demonstrates the Find operation: it locates the root of the set containing the selected node.
  2. The node I is not a root. The Find operation traverses up to the root.
  3. Visit each node on the path.
  4. The root of the current set is node A. The Find operation is not complete - the path needs to be flattened.
  5. Path compression is performed by linking all nodes on the path directly to the root.
  6. Path compression is complete, ending the Find operation.
  7. H and I now link straight to the root A, and the rank of A is still 3.
Union-Find — Find I with path compression. Last step: H and I now link straight to the root A, and the rank of A is still 3.

Path splitting and path halving are one-pass variants without recursion: they link each node on the path, or every other node, to its grandparent. Both keep the same bound.

What do path compression and union by rank do?

Both keep the trees flat, so a find walks few parent links. Union by rank puts the root of lower rank under the other, so a rank rises only when two trees of equal rank merge, and no rank exceeds log2 n. Path compression links every node a find walks straight to the root; together they bring each operation down to O(α(n)) amortized, almost constant.

Rank vs height: why path compression leaves the rank alone

Path compression never updates a rank, since finding the new height would mean measuring the root's other subtrees. A rank is therefore an upper bound on the height: a tree can be shorter than its rank, never taller, and the near-constant cost needs only that bound. That is why union by rank, not union by height, goes with path compression.

Union-find time complexity and the inverse Ackermann function

With n elements:

TechniqueOne find, worst caseAmortized per operation
NeitherO(n)O(n)
Union by rankO(log n)O(log n)
Path compressionO(n)O(log n)
BothO(log n)O(α(n))

α(n) is the inverse Ackermann function. The Ackermann function grows so fast that its inverse is at most 4 for any number of elements a computer could hold. The bound is amortized: one find can still walk a long path, but it flattens that path for the finds that follow. A union whose roots are known changes one link, in O(1). Space is O(n): one parent and one rank per element.

Union-find vs DFS and BFS for connected components

On a graph known in full, a depth-first or breadth-first search from each unvisited vertex labels every connected component in O(V + E). Union-find suits edges that arrive over time: each new edge is one union, and asking whether two vertices are connected takes two finds. It gives no path between them, ignores edge directions, and cannot split a set or delete an edge.

Union-find in Python, Java and C++

The app's listing follows the pseudocode above in all three languages, with a link to the full source on GitHub. Its recursive find is safe: by the rank bound, a million elements nest at most about 20 calls.

Note

In C++, union is a reserved keyword, so the app's C++ listing names the method union_sets.

The full source code is on GitHub, in Python, Java and C++.

Applications of union-find

  • Kruskal's minimum spanning tree: Kruskal's algorithm takes the edges from lightest to heaviest and skips each edge whose ends already share a root, since it would close a cycle.
  • Cycle detection in an undirected graph: union the ends of each edge in turn. The first edge whose ends already share a root closes a cycle.
  • Connected components: after one union per edge, each root stands for one component.
  • Interview problems: LeetCode 547, Number of Provinces, counts the components; LeetCode 684, Redundant Connection, is the cycle check above.

Three operations here.
Nine in the app, plus yours.

In VisiGrab, union-find runs nine prepared unions and finds on lettered trees with a message for every step, and lets you merge sets of your own.

Six more unions and finds

Buttons in the info dialog's Union and Find tabs start nine operations, the three on this page among them. In Union D and F, Union I and E and Union H and E, a find compresses a path before the two roots merge.

Nine sets of your own

The topic opens on nine single-node sets, A to I: tap two nodes in different sets and merge them step by step, until the app says all nodes are one set. An Operations log numbers every union and find so far.

Four tabs on how it works

Info, Union, Find and Efficiency: the forest and its roots, both rank rules with pictures, path compression and the fact that it leaves ranks alone, and the amortized cost with the inverse Ackermann function.

Python, Java and C++

One UnionFind class per language, with a recursive find that compresses the path and a union by rank, named union_sets in C++. Three numbered notes cover initialization, path compression and union by rank, and a link leads to the full source on GitHub.

Quiz

Ten questions, every option explained: what the sets are, how a root is recognized, what a merge changes, both rank rules, what a rank means, path compression and what it costs.

Kruskal, with its union-find drawn

The Kruskal topic draws a union-find of the graph's vertices together with the graph: each edge is checked by the sets of its ends, and every edge taken merges two roots.

Merge the sets,
flatten the paths.

Download VisiGrab to run nine unions and finds step by step, then merge the nine sets A to I yourself and watch the ranks grow.

Union-find is one of 30+ topics. See them all