Union-Find (also called Disjoint Set Union, DSU) is a data structure that tracks a collection of disjoint sets and supports two primary operations: find (determine which set an element belongs to) and union (merge two sets). It lives at the intersection of graph theory and algorithm design, serving as the backbone of Kruskal's MST algorithm, dynamic connectivity, and dozens of competitive programming problems. The key mental model is a forest of trees where each tree is a set and each tree's root is the set's representative β and the art of DSU lies entirely in how you keep those trees flat.
What This Cheat Sheet Covers
This topic spans 13 focused tables and 80 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Core Concepts and Terminology
The three-operation interface of DSU (make_set, find_set, union_sets) is deliberately minimal, yet it captures everything needed for equivalence-class reasoning. Understanding what a "representative," "root," and "parent array" mean is essential before studying optimizations.
| Technique | Example | Description |
|---|---|---|
parent = [0,1,2,3,4] (init) | β’ Array where parent[i] holds i's ancestorβ’ parent[i] == i marks a root (representative of its set). | |
parent[v] = v | β’ Initializes a single-element set β’ each element starts as its own root in O(1). | |
while v != parent[v]: v = parent[v]return v | β’ Climbs parent links until root β’ worst-case O(n) on a chain | |
parent[find(b)] = find(a) | β’ Merges two sets by attaching one root to the other β’ no balancing, can degenerate | |
find(x) == find(y) β same set | β’ The unique element satisfying parent[root] == rootβ’ used to check set membership |