Union-Find or DFS for connectivity?
“You need to answer connectivity questions on a graph. When do you use Union-Find, and when is DFS/BFS the better tool?”
What this tests
- Whether the candidate identifies the deciding factor: static graph vs incremental edges.
- Understanding of what Union-Find can and cannot do (no deletion, no path retrieval).
- Knowledge of the near-constant amortized bound and the two optimizations that produce it.
- Ability to name problems where each is the natural fit.
Strong answer
The deciding question is whether the graph is fixed or edges arrive over time. For a static graph, one Depth-First Search (DFS) or Breadth-First Search (BFS) pass labels every component in O(V + E), and afterwards any "same component?" query is an O(1) label comparison. That is optimal and simple. Union-Find (Disjoint Set Union) earns its place when edges are added incrementally and connectivity questions are interleaved with additions: each union or find is amortized O(α(n)) — effectively constant — so m operations cost O(m α(n)) without rerunning a traversal.
Union-Find is the natural fit for: Kruskal's Algorithm's MST (add edges in weight order, skip those that connect an already-connected pair), detecting the first edge that creates a cycle in an undirected graph (redundant-connection), dynamic "number of components after each addition", and grouping by equivalence (accounts with shared emails). DFS is the natural fit when you need more than connectivity: the actual path, cycle detection in a *directed* graph, topological order, bridges and articulation points, or bipartiteness — none of which Union-Find can answer.
A strong candidate knows the limitations: Union-Find does not support edge deletion (offline reversal or link-cut trees are needed for that), does not give paths, and only handles undirected connectivity. They can also explain that the α(n) bound requires both path compression and union by rank or size; with only one you get O(log n), with neither O(n) per operation in the worst case. And for grids — number-of-islands — they note either works, DFS being simpler for a static grid and Union-Find being the choice for the online variant where land cells are added one by one.
Green flags · Red flags
- Asks whether edges are static or arrive incrementally.
- States
O(V + E)for one traversal andO(α(n))amortized per Union-Find operation, and knows the two optimizations behind it. - Names Kruskal and cycle detection in undirected graphs as Union-Find's home turf.
- Lists what Union-Find cannot do: deletions, paths, directed cycles.
- Recognizes the online islands problem as the Union-Find variant.
- Uses Union-Find for directed-graph cycle detection.
- Reruns DFS after every edge insertion and calls it efficient.
- Claims Union-Find is
O(1)without qualification or cannot say what makes it near-constant. - Does not know that Union-Find cannot delete edges.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
q edge insertions on n nodes.