Algorithms and data structures · Intermediate

Union-Find: maintain components as sets merge

Track component membership through representatives, path compression, and size-based union.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Represent membership through a chosen representative
  2. Follow connectivity as relationships are added
  3. Combine a merge rule with path compression
  4. Recognize which queries require another structure
  5. Ask Logeia about this articleCheck your understanding

Represent membership through a chosen representative

Union-Find maintains membership in disjoint sets. Initially, each element forms a singleton set. The find operation obtains the representative of the set containing an element, and union merges two sets. A forest implementation stores a parent link for every element and uses a root as the representative. Two elements belong to the same set when their representatives agree. The root’s identifier need not carry application meaning, and the chosen representative can change after a merge. Applications should rely on the membership relation, not on one particular element remaining the leader.

Follow connectivity as relationships are added

Begin with {A}, {B}, {C}, and {D}. After union(A, B), one component is {A, B}; union(C, D) produces {C, D}. Applying union(B, C) then places all four elements in one component. A and D are connected even though no direct A-to-D edge was inserted. The internal parent forest is an efficient representation of set membership, not a record of the original graph edges. Consequently, following its parent links does not in general recover a real path in the input graph.

Combine a merge rule with path compression

Union by size attaches the smaller component’s root below the larger one, avoiding unnecessarily deep trees. Union by rank uses a related height estimate. During find, path compression redirects traversed elements toward the root to shorten later searches. Combining suitable union rules with compression gives a very small amortized cost described using the inverse Ackermann function α(n). That is a bound over a sequence of operations, not an unconditional worst-case constant bound for each individual call. Initialization still has work proportional to the number of elements, and the parent and size or rank arrays occupy linear space.

Recognize which queries require another structure

Union-Find suits incremental connectivity in an undirected graph and the cycle-avoidance test used by Kruskal’s spanning-tree algorithm. Its basic operations merge sets; they do not split a component when an edge is deleted. Fully dynamic connectivity therefore needs additional machinery. Enumerating every element in a component or recovering an actual route between vertices is also not directly supplied by the basic parent array. Furthermore, find can mutate internal state through path compression. Concurrency, persistent versions, or rollback requirements can change the appropriate implementation, so those needs should be stated before selecting the usual fast variant.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path