Union Find

Tactic

Union find tracks which elements belong to the same connected component as edges arrive. It supports find to get a representative and union to merge two components.

The invariant is component identity. Two elements are connected exactly when their representatives match. Path compression and union by rank keep representative lookup nearly constant in practice.

Use union find when connectivity only grows. Each new edge can merge components or reveal that the edge connects two nodes already in the same component.

Value

The value is avoiding repeated graph traversals after every edge. Instead of asking BFS to rediscover a component, the structure maintains components incrementally.

Direct complexity example

Brute force: After each edge, run DFS or BFS to test connectivity: $O(E(V + E))$ time in the worst case.
With this tactic: Use find and union per edge: near $O(E)$ time in practice, more precisely $O(E \alpha(V))$ with standard optimizations.
Space: Space is $O(V)$ for parent and rank or size arrays.

Challenges this solves

connected components
redundant connection
accounts merge
minimum spanning tree
offline grid connectivity

When to use it

Use this tactic when these conditions are true:

edges are added over time
you need to know whether two nodes are already connected
components only merge, not split
cycle detection in an undirected graph is needed

When not to use it

Reach for a different tactic when these warning signs appear:

edges are deleted online
you need shortest paths or traversal order
the graph is directed and reachability is not symmetric
component membership depends on labels that change after merging

Terminology clues

These prompt words often point toward this concept:

union
find
connected components
same set
redundant edge
merge accounts
Kruskal
disjoint set