Union-Find (Disjoint Set Union)

What problem this solves — and why BFS/DFS isn't always the answer

Union-Find (also called Disjoint Set Union, or DSU) answers one question extremely efficiently: "are these two elements in the same connected component?" — and it lets you add edges one at a time while answering that question after every addition. You could answer the same question by re-running BFS/DFS from scratch after every new edge, but that costs O(V + E) per query. If you have Q queries interleaved with edge additions, that's O(Q · (V + E)) — often too slow. Union-Find answers each query and each edge addition in near-O(1) amortized time, making the total cost close to O(V + Q) instead.

This is the key signal for reaching for Union-Find over a fresh BFS/DFS: dynamic or incremental connectivity — the edge set grows over time (or you're deciding whether to add edges one by one, as in Kruskal's algorithm) and you repeatedly need "are these connected right now?" If the graph is static and you only need connectivity once, a single BFS/DFS pass to label components is simpler and just as fast asymptotically.

The data structure: a parent-pointer forest

Each element starts as its own set, represented as a tree where every node points to a parent, and a set's canonical representative ("root") is a node that is its own parent.

The two optimizations that make it fast

Neither optimization alone is enough; together they're what gets you to near-constant time.

• Path compression (in find): every time you walk up to the root, re-point every node along that path directly to the root. Future find calls on those nodes become O(1). Without this, find degrades to O(n) on a skewed tree (imagine unioning 0-1, 1-2, 2-3, ... — you'd get a long chain).
• Union by rank (or size): when merging two trees, always attach the shorter (or smaller) one under the taller (or larger) one's root, rather than arbitrarily. This keeps the trees shallow — without it, an adversarial sequence of unions can still build a long chain even with path compression helping after the fact.

With both optimizations, a sequence of m operations on n elements runs in O(m · α(n)) total, where α is the inverse Ackermann function — a value that grows so slowly it is less than 5 for any n you could ever construct in practice (it doesn't exceed 4 until n exceeds the number of atoms in the observable universe). In interviews, it's standard and expected to simply call this O(α(n)) amortized per operation, effectively O(1) — you don't need to derive or prove the Ackermann bound, just know it exists and why (Tarjan, 1975) and that path compression + union by rank/size together is what earns it.

Why "near-O(1)" beats BFS/DFS for this specific shape of problem

Picture "Redundant Connection": edges are added to a graph one at a time, and you must find the first edge that creates a cycle. With Union-Find, this is a single pass: for each edge (u, v) in order, call union(u, v); the first time union returns False, that edge closes a cycle — because u and v were already connected before this edge was considered, so this edge is redundant. That's O(E · α(V)) total. Re-running BFS/DFS from scratch after each edge to check "would this create a cycle?" would cost O(E · (V + E)) — asymptotically much worse, and the difference is exactly the amortized-near-constant-time guarantee Union-Find provides for incremental connectivity.

Complexity, precisely

• find and union: O(α(n)) amortized each, with both path compression and union by rank/size applied. (With only one of the two optimizations, you get O(log n) amortized — still good, just not optimal.)
• Initialization: O(n) to set up the parent array.
• Space: O(n).

Pitfalls and interview gotchas

• Implementing find without path compression. It still works, but degrades toward O(n) per call on adversarial inputs — always compress paths unless you have a specific reason not to (there almost never is one).
• Union by rank/size vs. arbitrary attachment. Attaching roots arbitrarily (e.g., always parent[find(a)] = find(b)) without tracking rank or size can build long chains that path compression only partially mitigates. Always union by rank or size in interview code — it's a two-line addition that changes the complexity class.
• Off-by-one on element count. Many problems index nodes from 1 to n (city numbers, course numbers), not 0 to n-1 — size your parent array as n + 1 and simply ignore index 0, rather than remapping everything and risking an indexing bug under time pressure.
• Forgetting that union returning False is meaningful, not just a no-op. In cycle-detection problems (Redundant Connection) and MST construction (Kruskal's), that boolean is the answer signal — discard it and you've thrown away the one piece of information the problem is asking for.
• Assuming Union-Find can handle edge removal. It fundamentally cannot — once two sets are merged, there's no cheap way to split them back apart. If a problem needs "connectivity under both additions and removals," Union-Find alone won't work; that calls for more advanced techniques (offline processing in reverse, for one) that are out of scope for a standard interview.
• Confusing "same component" with "same value/label." Union-Find tracks structural connectivity through union operations you explicitly perform — it does not automatically know that two nodes with the same string, email, or attribute should be merged. In problems like Accounts Merge, you must decide which elements to union based on shared attributes; the data structure only tracks the consequence.
• Directed graphs. Union-Find models undirected connectivity by nature — merging a and b treats them symmetrically. It cannot directly detect cycles in a directed graph (a back edge in a directed graph doesn't necessarily mean the two endpoints are "already connected" in the undirected sense the structure tracks). For directed cycle detection, use the DFS three-color technique from Topological Sort instead.

Union-Find vs. BFS/DFS for connectivity: decision table

Question	Prefer
Static graph, need connectivity once	BFS/DFS (simpler, same O(V+E))
Edges added incrementally, need connectivity after each addition	Union-Find
Need to detect the cycle-forming edge as edges arrive in a fixed order	Union-Find
Need actual shortest path, not just "connected or not"	BFS/DFS (Union-Find doesn't track paths or distances)
Directed graph cycle detection	DFS three-color (Topological Sort)
Building a Minimum Spanning Tree by considering edges in weight order	Union-Find — this is exactly Kruskal's algorithm

Where this reappears

Union-Find is the engine inside Kruskal's Minimum Spanning Tree algorithm (Advanced Niche Algorithms — process edges in ascending weight order, union if and only if it doesn't close a cycle) — read this subtopic first, because Kruskal's is essentially "Redundant Connection run backwards with a cost-minimization goal bolted on." It's also a common alternative to grouping-by-hash-map whenever "grouping" is really "connectivity" in disguise, as in Accounts Merge.