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.

The 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

Tiny worked example

Start with every vertex in its own set.
When an edge `(u,v)` arrives, compare `find(u)` and `find(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 this kind of problem

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.