Union-Find (disjoint set)

In short: Union-Find manages groups of elements and answers very quickly whether two elements belong to the same group and how to merge two groups.

In more detail: Each group is stored as a tree whose root represents the group. find(x) follows parents up to the root, union(a, b) attaches one root under the other.

In Depth

• Path compression: During find, visited nodes are attached directly under the root. Later lookups become almost instant.
• Union by rank/size: The smaller tree goes under the larger one so trees stay flat.
• Runtime: Practically constant (inverse Ackermann function) per operation.
• Use: Connected components, Kruskal’s algorithm for minimum spanning trees, detecting cycles in undirected graphs.
• Limit: Groups can be merged but not split again.

See also: Graph (data structure)