# Union-Find (Disjoint Set Union) > Union-Find (disjoint set union) answers 'are these two nodes connected?' in near-constant time. Master path compression, union by rank, and Kruskal's MST. Canonical: https://ironclad.academy/dsa/structures/union-find | Difficulty: medium | Topics: Union-Find, Disjoint Set Union, Graphs, Trees, Data Structures Asked at: Google, Amazon, Meta ## Key takeaways - Union-Find maintains a forest of trees where each tree is one connected component; find() returns the root (the component representative). - Path compression flattens the tree on every find, making future finds on the same nodes instant — the path collapses to depth 1. - Union by rank always attaches the shorter tree under the taller root, preventing the degenerate chain that kills naive union-find performance. - Together, both optimizations achieve O(α(n)) amortized per operation — inverse-Ackermann, which is effectively constant for any real input. - The tell for Union-Find in an interview: "connected components," "same group," "detect cycle," "merge X and Y" — any problem that is dynamically grouping elements and testing membership. > **In one line:** Union-Find maintains a forest of disjoint trees — one tree per connected component — letting you merge two components or test whether two elements share one in nearly O(1) time. You have a million user accounts. Some share an email, some share a phone number. You need to merge them into canonical identities and later answer "are account A and account B the same person?" You could build a [graph](/dsa/structures/graph) and BFS every time someone asks. Or you could use Union-Find, answer each query in effectively constant time, and feel smug about it. That's the pitch. Union-Find is the structure for **dynamic connectivity**: groups that start separate and merge together over time, where you need to test membership cheaply after each merge. [Interactive visualizer on the original page: graph — three components — run BFS from any node and it stops at the boundary] The nodes above sit in three separate clusters. Run a traversal from any node and it dies at the edge of its own cluster — that boundary *is* the component. Each union operation would connect two clusters. Union-Find's job is to track which cluster every node belongs to without re-running that traversal each time someone asks. **The core facts:** - Starts with n singletons — every element is its own group. - `union(a, b)` merges the groups containing a and b. - `find(a)` returns the root (representative) of a's group. - `connected(a, b)` is just `find(a) == find(b)`. - With path compression + union by rank: every operation is O(α(n)) amortized — functionally O(1). ## The mental model: a messy family tree Each group is a tree. The root of the tree is the group's representative — its "ID." Every node knows its parent. To ask "what group is node x in?" you climb up parent pointers until you hit a root (a node that is its own parent). To merge two groups, you make one root the parent of the other. Start naive: everyone's own parent. ``` parent: [0, 1, 2, 3, 4] index: 0 1 2 3 4 ``` Union(0, 1): make 0 the parent of 1. Union(1, 2): make 0 the parent of 2 (after finding 0 is 1's root). Union(3, 4): make 3 the parent of 4. Two components now: {0, 1, 2} and {3, 4}. ```mermaid flowchart TD A0["0 (root)"] A1["1"] A2["2"] B3["3 (root)"] B4["4"] A0 --> A1 A0 --> A2 B3 --> B4 style A0 fill:#7c5cff,color:#fff style B3 fill:#22d3ee,color:#0a0a0f ``` `find(2)` walks 2 → 0 and returns 0. `find(4)` walks 4 → 3 and returns 3. `connected(2, 4)` compares 0 ≠ 3: false. Union(2, 4) merges them — now one component with root 0. This is correct. But naive union-find has a fatal flaw: if you always union in one direction, the tree becomes a chain. `find` on the deepest node walks the entire chain — O(n) per operation, O(n²) total for n unions. The fix is two optimizations. Together they're the whole magic. ## The two optimizations that make it fast ### 1. Union by rank When merging two trees, always attach the **shorter** one under the **taller** root. "Rank" tracks an upper bound on tree height — it's not the exact height, just a conservative estimate. ```python def union(self, a, b): root_a = self.find(a) root_b = self.find(b) if root_a == root_b: return False # already same component # attach shorter tree under taller root if self.rank[root_a] < self.rank[root_b]: root_a, root_b = root_b, root_a self.parent[root_b] = root_a if self.rank[root_a] == self.rank[root_b]: self.rank[root_a] += 1 return True ``` Why does this keep trees shallow? Because a tree of rank r must contain at least 2^r nodes — you can prove this by induction. If the tree has rank r, it was formed by merging two trees of rank r-1, each with at least 2^(r-1) nodes. So the tree has at least 2^r. That means rank ≤ log₂(n), and find walks at most log n steps. With union by rank alone, you're at O(log n) per operation — already good. ### 2. Path compression During `find`, as you climb from node to root, rewire **every node you touch** to point directly at the root: ```python def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x] ``` One line. The recursive call finds the root; the assignment flattens the path. Next time any node on that path calls `find`, it's a single hop to the root. ```mermaid flowchart LR subgraph "Before find(4)" direction TB R0["0 (root)"] --> N1["1"] --> N2["2"] --> N3["3"] --> N4["4"] end subgraph "After find(4) — path compressed" direction TB R0b["0 (root)"] R0b --> N1b["1"] R0b --> N2b["2"] R0b --> N3b["3"] R0b --> N4b["4"] end style R0 fill:#7c5cff,color:#fff style R0b fill:#7c5cff,color:#fff style N4 fill:#00ff9d,color:#0a0a0f style N4b fill:#00ff9d,color:#0a0a0f ``` The tree on the left is the chain that union by rank prevents — but path compression fixes even that case. After one `find(4)`, the entire chain collapses to depth 1. ### Together: inverse-Ackermann Combine both optimizations and the amortized cost per operation is O(α(n)), where α is the inverse-Ackermann function. α(n) is the answer to "how many times can I apply the Ackermann function before exceeding n?" It grows so ludicrously slowly that α(2^65536) = 5. For n up to 10^80 — more atoms than the observable universe — α(n) ≤ 5. You treat it as O(1) and feel no guilt about it. The formal proof is in Tarjan's 1975 paper. The practical takeaway: **just use both optimizations and call each operation constant.** ## The complete implementation ```python class UnionFind: def __init__(self, n): self.parent = list(range(n)) # every node is its own parent self.rank = [0] * n # all trees start at rank 0 self.components = n # track component count def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x] def union(self, a, b): root_a, root_b = self.find(a), self.find(b) if root_a == root_b: return False # same component, no merge needed # union by rank: attach smaller tree under larger root if self.rank[root_a] < self.rank[root_b]: root_a, root_b = root_b, root_a self.parent[root_b] = root_a if self.rank[root_a] == self.rank[root_b]: self.rank[root_a] += 1 self.components -= 1 return True def connected(self, a, b): return self.find(a) == self.find(b) def num_components(self): return self.components ``` This is the template. Copy it into your interview and you're 80% done. The rest is figuring out what nodes and edges to feed it. ## Complexity table | Operation | Time | Space | |---|---|---| | `__init__(n)` | O(n) | O(n) | | `find(x)` | O(α(n)) amortized; a single call can walk O(log n) pointers | O(log n) recursion stack — O(1) if written iteratively | | `union(a, b)` | O(α(n)) amortized | same stack as find (it calls find twice) | | `connected(a, b)` | O(α(n)) amortized | same stack as find | | m operations total | O(m · α(n)) | O(n) | For comparison: a naive union-find (no optimizations) is O(n) per find. Union by rank alone is O(log n). Both together is O(α(n)). The jump from O(log n) to O(α(n)) is the path-compression win. ## Worked problems ### Problem 1: Number of connected components Given n nodes and a list of undirected edges, count the components. This is Union-Find in its purest form. ```python def count_components(n, edges): uf = UnionFind(n) for a, b in edges: uf.union(a, b) return uf.num_components() ``` One pass over edges, each union is O(α(n)), done. For a one-shot static count like this, a single BFS/DFS pass is equally good and arguably simpler — union-find earns its keep when edges keep arriving and connectivity queries interleave with them. But when a problem hands you an edge list and asks for a count, the five-line version above is hard to beat at the whiteboard. ### Problem 2: Redundant connection (LeetCode 684) Given a graph that starts as a tree and has exactly one extra edge added, find the redundant edge. The tell: the first edge whose two endpoints are **already connected** before you process it is the cycle-creating edge. ```python def find_redundant_connection(edges): n = len(edges) uf = UnionFind(n + 1) # nodes are 1-indexed for a, b in edges: if not uf.union(a, b): return [a, b] # union returned False → already connected → cycle return [] ``` `union` returns False only when `find(a) == find(b)` — the two nodes are already in the same component, so this edge creates a cycle. Processing edges in order guarantees we return the last such edge — the one the problem says is redundant. Time: O(n · α(n)). Space: O(n). Process each edge. The moment `union` returns false, you've found the edge that closes a cycle. No DFS needed, no visited tracking — one pass, nearly O(n). ### Problem 3: Accounts merge (LeetCode 721) This is Union-Find on strings, which trips people up because they reach for a [graph](/dsa/structures/graph) + [DFS](/dsa/techniques/dfs-patterns). Given a list of accounts where each account is `[name, email1, email2, ...]`, merge accounts that share at least one email. Return the merged accounts with emails sorted. The key insight: **emails are the nodes**. Two emails in the same account are in the same component. Union every email in an account to the first email of that account. ```python from collections import defaultdict def accounts_merge(accounts): parent = {} size = {} def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(a, b): ra, rb = find(a), find(b) if ra == rb: return if size[ra] < size[rb]: # union by size — keep the tree shallow ra, rb = rb, ra parent[rb] = ra size[ra] += size[rb] email_to_name = {} for account in accounts: name = account[0] # initialize each email as its own singleton for email in account[1:]: if email not in parent: parent[email] = email size[email] = 1 email_to_name[email] = name # union all emails in this account to the first for email in account[2:]: union(account[1], email) # group emails by their root components = defaultdict(list) for email in parent: components[find(email)].append(email) result = [] for root, emails in components.items(): result.append([email_to_name[root]] + sorted(emails)) return result ``` The trick: you don't need numeric indices. The parent dict works directly on string keys. This is a common adaptation — Union-Find with a hash map instead of an array when your nodes aren't consecutive integers. Don't drop the balancing to save three lines. The tempting shortcut — `parent[ra] = rb` with no size check — lets accounts that chain pairwise (a@x with b@x, b@x with c@x, ...) build a parent chain thousands of links deep before compression touches it, and the recursive `find` then blows past Python's default 1,000-frame recursion limit. Union by size keeps the depth logarithmic; an iterative two-pass find is the other escape hatch. ### Problem 4: Kruskal's minimum spanning tree Union-Find is the engine inside Kruskal's MST algorithm. You want the cheapest set of edges that connects all nodes. Strategy: sort edges by weight, add each edge if it connects two different components (i.e., doesn't create a cycle). Stop when you have n-1 edges. ```python def kruskal_mst(n, edges): # edges: list of (weight, u, v) edges.sort() uf = UnionFind(n) mst_weight = 0 mst_edges = [] for weight, u, v in edges: if uf.union(u, v): # False means same component → skip mst_weight += weight mst_edges.append((u, v)) if len(mst_edges) == n - 1: break # MST complete return mst_weight, mst_edges ``` The cycle detection is exactly what Union-Find does for free: `union` returns False when both endpoints are already connected. Sorting edges is O(E log E). Each union/find is O(α(n)). Total: O(E log E) — the sort dominates. Good enough for every interview; asymptotically faster MST algorithms exist (Prim with a good heap wins on dense graphs), but nobody writes them under time pressure. See also [topological sort](/dsa/techniques/topological-sort) for another graph ordering algorithm with a similar "process edges in a controlled order" structure. ## The patterns that signal Union-Find You've been doing a BFS or DFS in your interviews when Union-Find would be cleaner. Here's the tell: | Problem says... | Reach for... | |---|---| | "number of connected components" | Union-Find | | "detect a cycle in an undirected graph" | Union-Find | | "merge accounts / identities / groups" | Union-Find | | "minimum spanning tree" | Union-Find (Kruskal) | | "add edges one at a time, query connectivity" | Union-Find | | "are X and Y in the same group?" | Union-Find | | "grid problems: count islands, flood-fill variants" | BFS/DFS or Union-Find | The grid question deserves elaboration. [DFS patterns](/dsa/techniques/dfs-patterns) on a grid are fine — often simpler to code. But if the grid is enormous and connectivity queries come in batches after partial construction, Union-Find is faster because it doesn't re-traverse. ## Pitfalls and anti-patterns **Forgetting to call find before comparing parents.** Never compare `parent[a] == parent[b]` directly. Two nodes can be in the same component with different parent values — you need to find the root. Always `find(a) == find(b)`. **Using union by size instead of rank incorrectly.** Both work. Union by size (count of nodes, not estimated height) is equally valid and some people find it more intuitive. Pick one and stick to it — mixing them in a single implementation is a common source of subtle bugs. **Re-initializing UnionFind inside an inner loop.** If your outer loop is over test cases and your inner loop processes edges, initialize once per test case, not once per edge. This sounds obvious but shows up constantly under interview pressure. **Calling union when you only need find.** `union(a, b)` should only be called when you want to permanently merge two groups. If you're answering a read-only query, call `connected(a, b)` (two finds). Calling union accidentally merges groups you didn't intend to merge — and there's no undo. **Off-by-one in 1-indexed problems.** LeetCode graph problems often give nodes numbered 1 to n. Your parent array needs size n+1. This bites a lot of people who initialize `UnionFind(n)` and then wonder why node n is out of bounds. **Trying to split a component.** Union-Find only merges — it can't split a group once merged. If you need dynamic connectivity with both adds and removals, look at link-cut trees. They're significantly more complex and rarely asked in interviews. ## When NOT to use Union-Find Union-Find is not a graph search algorithm. It tells you **whether** two nodes are connected, not **how** they're connected, **what path** exists between them, or **what the shortest path** is. | You need | Use instead | |---|---| | Shortest path between two nodes | BFS (unweighted), Dijkstra (weighted) | | All paths between two nodes | DFS with backtracking | | Topological ordering of a DAG | [Topological sort](/dsa/techniques/topological-sort) | | Strongly connected components | Tarjan's / Kosaraju's algorithm | | Detect cycle in a directed graph | DFS with color marking — Union-Find gets this wrong for directed edges | | Split / remove connections | Link-cut trees (not an interview topic) | | Minimum spanning tree with frequent edge-weight updates | Prim's algorithm may be more natural | That directed-graph gotcha is worth repeating. Union-Find treats all edges as undirected. If you feed it a directed graph's edges, it will happily merge components that aren't actually mutually reachable. For cycle detection in a directed graph, DFS with a three-color visited array is the right tool. See [DFS patterns](/dsa/techniques/dfs-patterns) for that. Also: if the graph is static and you need component membership once, a single BFS or DFS pass is O(V+E) and simpler to write. Union-Find's advantage is dynamic updates — if there are no updates, the overhead isn't buying you anything. --- Union-Find is one of the few data structures where understanding the theory directly makes you faster in practice. Path compression and union by rank aren't just academic niceties — without them you have an O(n²) algorithm wearing an O(1) costume. Learn both optimizations cold, memorize the template above, and you'll recognize the "are these two things connected?" shape in problems that superficially look nothing like a graph. The accounts merge problem doesn't scream "union-find" until you've seen it once. After that, it's obvious every time. ## Frequently asked questions Q: What is Union-Find used for? A: Union-Find answers one question efficiently: are these two elements in the same group? The classic use cases are finding connected components in a graph, detecting cycles, running Kruskal's minimum spanning tree algorithm, merging accounts or identities that share some attribute, and any problem where you need to group things dynamically and query group membership later. It shines when you need many union and find operations interleaved — something a plain BFS or DFS cannot match without re-scanning the graph. Q: What is path compression in Union-Find? A: Path compression is an optimization applied during the find operation. When you follow parent pointers up to the root, you retroactively rewire every node you passed through to point directly at the root. The path collapses to depth 1 after the first traversal, so future finds on any of those nodes cost O(1). Without path compression, find can degrade to O(n) on a chain-shaped tree. With it, amortized cost drops to nearly constant. Q: What is union by rank and why does it matter? A: Union by rank (also called union by height) always attaches the shorter tree under the root of the taller one. This keeps the tree balanced. Without it, repeatedly unioning in one direction produces a chain — find then walks n nodes, making each operation O(n). With union by rank alone (no path compression), find is O(log n). Combine both optimizations and you get the inverse-Ackermann O(α(n)) bound. Q: What is inverse-Ackermann time complexity? A: The inverse-Ackermann function α(n) grows so slowly it is effectively a constant for all practical inputs. α(2^65536) is still only 5. So when you see O(α(n)) for Union-Find with both optimizations, it means "amortized constant time" in every real scenario you will ever encounter. The theoretical distinction from O(1) only matters in proofs; in practice you can treat each union/find as O(1). Q: When should I use Union-Find instead of BFS or DFS for connectivity? A: Use Union-Find when you need to answer many connectivity queries on a graph that is being built incrementally (edges arrive one at a time), or when you need to repeatedly ask "are X and Y connected?" after a series of merges. BFS/DFS finds components in O(V+E) but you have to re-run it if the graph changes. Union-Find handles each edge addition and each query in O(α(n)) amortized. If the graph is static and you only need one pass, BFS/DFS is simpler. If it is dynamic, Union-Find wins.