Union-Find Explained: Track Connected Components

By Hourly DSA · October 2, 2026 · 4 min read

Union-find tracks which items belong to the same connected group as connections are added. It is also called a disjoint-set data structure. Its two main operations ask which group contains an item and merge two groups.

Think of a network that gains one connection at a time. You want to answer whether two vertices are connected without searching the whole network after every addition.

Begin with separate groups

Start with five vertices: A, B, C, D, and E. With no edges, each vertex forms its own component.

Add three undirected edges:

A — B
C — D
B — C

After the first edge, the groups are {A, B}, {C}, {D}, and {E}. The second produces {A, B}, {C, D}, and {E}. The third joins the first two groups, leaving {A, B, C, D} and {E}.

A and D are connected even though there is no direct edge between them. Connectivity means a path exists, not that the vertices are neighbors.

A representative identifies the group

Each item stores a parent. Following parents eventually reaches a root whose parent is itself. That root represents the component.

find(A) returns A's root. Two vertices belong to the same group exactly when their roots match.

The representative is an implementation choice. If A represents {A, B, C, D}, that does not mean every original graph edge touches A. The parent structure records membership, not the actual path between vertices.

This distinction matters if the question asks you to print a route. Union-find alone does not retain enough information to reconstruct one.

Union joins roots, not arbitrary vertices

To connect B and C, find both roots first. If the roots differ, make one root a child of the other. The two components become one.

If the roots already match, there is nothing to merge. A component counter decreases only after a successful merge, not after every edge.

Starting from five components, our three successful merges leave two. Adding A–D afterward leaves the count at two because those vertices are already connected.

Detect an undirected cycle

Before adding A–D, a path already connects A to D through B and C. Adding the extra edge closes a cycle.

For a simple undirected graph processed one edge at a time, equal roots before a new edge therefore signal a cycle. Unequal roots mean the edge joins separate components.

Don't transfer that rule directly to directed graphs. Direction changes which paths exist. For directed prerequisite cycles, topological sorting answers a different question using incoming dependencies.

Keep the parent trees shallow

Careless merges can create a long chain, making a find operation take linear time.

Two common improvements work together:

Union by size: attach the smaller component's root beneath the larger one's root.
Path compression: during find, redirect visited items toward the root so later searches have less distance to travel.

With both improvements, operations have O(α(n)) amortized cost, where α is the inverse Ackermann function. It grows extremely slowly, but the bound is amortized rather than a promise that every individual operation takes constant time. Initializing n items takes O(n) time and space.

Know when traversal is simpler

For a fixed graph and one request to list its components, BFS or DFS is often the simpler choice. Union-find is especially useful when edges arrive incrementally and you repeatedly ask whether endpoints share a component.

Basic union-find does not efficiently undo arbitrary edge deletions. Removing a connection might split a component, and parent pointers do not describe how to recover that split.

Check one extra edge

After our three original edges, does adding D–E create a cycle?

No. E is still separate. The edge merges two components, leaving one connected group.

That distinction between joining groups and closing a path is a useful recognition question to practice with Hourly DSA.