Algorithms / Union Find Connectivity
Least You Need to Know: Union-Find for Connectivity and Cycles
Union-find, also called disjoint set union (DSU), tracks which items currently belong to the same connected component. It is especially useful when edges are added over time and you need fast connectivity or redundant-edge reasoning.
Least you need to know
- Each set has a representative root, and
find(x)returns the representative of x's current component. - Two nodes are connected exactly when their representatives are the same.
- When an undirected edge connects two vertices already in the same component, that edge creates a cycle.
- Path compression and union by rank or size make repeated operations very fast in practice.
- Union-find is best for dynamic connectivity under edge additions, not for general shortest-path questions.
Key notation
- find(x) — representative of the set containing x
- union(x, y) — merge the sets containing x and y
- component — a maximal connected piece under the processed edges
Worked example
- Start with every vertex in its own set.
- When an edge
(u,v)arrives, comparefind(u)andfind(v). - If the representatives differ, union the two sets.
- If the representatives are already equal, the new undirected edge closes a cycle inside an existing component.
Common mistakes
- Students often use union-find for shortest paths even though it only answers connectivity-style questions.
- Students often forget that cycle detection with union-find is most natural for undirected graphs with added edges.
- Students often describe path compression as changing the connected components when it only speeds up future finds.
How to recognize it
- Edges are added one by one and the prompt asks whether two nodes are connected yet.
- The question asks for the first redundant edge in an undirected graph.
- You only need connectivity or component membership, not a full traversal order.
Next recommended lesson
Continue through this topic with Least You Need to Know: Z-Function, Prefix Matches, and Pattern Search by Concatenation.
Least You Need to Know: Z-Function, Prefix Matches, and Pattern Search by ConcatenationRelated lessons
Keep going with nearby lessons in the same topic.