When is Union-Find the right pattern?

Category: DSA Patterns

Answer

Union-Find groups elements into disjoint sets and answers “are x and y in the same group?” in near-constant time (inverse Ackermann). Use it for connected components, redundant edges, accounts merge, percolation, friend circles.

Concrete examples from the fca project context

Example 1

Redundant Connection: union each edge; the first edge whose endpoints are already connected is redundant.

Example 2

Accounts Merge: union emails by shared account; gather per root.

Example 3

Number of Provinces: union on adjacency; count distinct roots.

Data flow / flow chart

find(x) -> root
  union(a, b): connect roots unless already same
  connected(x, y)? -> find(x) == find(y)

Takeaway

Union-Find for disjoint-set merges. Use DFS/BFS only when you need the path.