Union Find (Disjoint Set) · Data Structures & Algorithms

Edges show up one at a time, and after each one someone wants to know whether two nodes now sit in the same group. Answer that with DFS or BFS and you re-traverse the entire graph on every single edge, which collapses the moment the graph gets big. Union Find is the data structure that handles the streaming version of the question. It tracks connected components as the edges arrive, and once you bolt on path compression and union by rank, every query and every merge costs almost nothing, effectively O(1).

Union Find (Disjoint Set Union / DSU) answers one question efficiently: "Are these two elements in the same group?"

With path compression and union by rank, operations are nearly O(1), technically O(α(n)) where α is the inverse Ackermann function, effectively constant.

The Core Idea

The whole structure is a pile of disjoint sets and two operations. One tells you which set an element lives in, the other fuses two sets into one:

Each element belongs to a set, identified by a "representative" (root). Two elements are in the same set if they have the same root.

Operations:
- find(x): Return the root of x's set
- union(x, y): Merge the sets containing x and y

Example: Connect 1-2, then 2-3, then 4-5

Initial: {1} {2} {3} {4} {5} (each is its own set)
union(1,2): {1,2} {3} {4} {5}
union(2,3): {1,2,3} {4} {5}
union(4,5): {1,2,3} {4,5}

find(1) == find(3)? Yes (same set)
find(1) == find(4)? No (different sets)

Basic Implementation

Think of a forest where every element begins as its own one-node tree, pointing at itself. The parent array is the whole thing: parent[x] = x means x is the root of its own tree. find(x) follows parent pointers upward until it reaches a node that points to itself, and that self-pointing node is the root, the representative for the entire group.

union(x, y) finds the root of each element's tree and points one root at the other, welding the two trees into one. Once that happens, every element in both trees traces its parent chain back to the same root, which is exactly how the structure decides they belong together. What trips people up on a first read is that you never touch the individual elements. Connect the two roots and every node underneath comes along for free:

python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # Each element is its own root
    
    def find(self, x):
        while self.parent[x] != x:     # Follow parent pointers
            x = self.parent[x]
        return x                       # Reached the root
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y  # Connect the two trees

This is correct, and it's also slow. Nothing stops the chains from growing long, and a long chain makes find O(n). Two optimizations kill that off, and you almost always want both.

Optimization 1: Path Compression

Path compression is the optimization that earns Union Find its reputation. Once find(x) has walked the whole chain from x up to the root, leaving that chain intact for the next call to re-walk is pure waste. You already hold the root in your hand, so point every node you passed straight at it. One slow traversal buys you O(1) on every future find for any of those nodes.

Concretely: if the path is 5 -> 4 -> 3 -> 2 -> 1 (root), after find(5) with path compression, the parent array changes from [1, 1, 2, 3, 4] to [1, 1, 1, 1, 1]. Nodes 2, 3, 4, and 5 all point directly to 1. The next call to find(3) doesn't walk 3 -> 2 -> 1. It goes straight to 1 in one step.

This is amortization in its purest form. The first find on a deep chain pays O(depth), but it flattens the tree permanently, so every find after it on those nodes is O(1). You spend one expensive operation to make a crowd of future ones cheap. Run a handful of operations and the trees are nearly flat anyway, most nodes sitting one hop from their root.

python

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # Flatten path to root
    return self.parent[x]                            # Return root

Recursion depth can bite you here, since Python caps out around 1000 frames and a big input will blow past that. The iterative version gets the same flattening in two explicit passes: walk up once to locate the root, then walk the path a second time rewriting every parent pointer to point straight at it:

python

def find_iterative(self, x):
    root = x
    while self.parent[root] != root:  # First pass: find root
        root = self.parent[root]
    
    while self.parent[x] != root:     # Second pass: compress path
        next_x = self.parent[x]
        self.parent[x] = root         # Point directly to root
        x = next_x
    
    return root

Once the path is compressed, every node on it points straight at the root and future finds are O(1). The flattening, step by step:

Before: A tall chain

Nodes 1-2-3-4-5 form a long chain. find(5) must walk 4 steps to reach root 1. This is the worst case for find, O(n).

root

parent: [1, 1, 2, 3, 4]. Each points to the one above

Optimization 2: Union by Rank/Size

Compression cleans up tall trees after they form. Union by rank keeps them from forming at all. Left to its own devices, a naive union will happily bolt the bigger tree onto the smaller one and grow a chain. Merge elements 1 through 5 in order and watch: union(1,2) points 2 at 1, union(1,3) points 3 at 1, and you've got a tidy star. Do union(2,3), union(3,4), union(4,5) instead and you've built the chain 2 -> 3 -> 4 -> 5, which drags find back to O(n) until compression has a chance to fire.

Rank fixes the ordering by always hanging the shorter tree under the taller one. If tree A stands 3 tall and tree B stands 1, attaching B under A's root leaves A's height untouched, since B's nodes just gain a level above them and the deepest path is still 3. Go the other way, A under B, and you'd manufacture depth 4 for no reason.

Height only has to grow in one situation: two trees of equal rank. If both are height 2, whichever goes under the other, you end up at height 3, so you pick one arbitrarily and bump its counter. A tree therefore gets taller only when two equal-rank trees merge, and that can happen at most O(log n) times because each bump requires the tree to double in size. That single fact is why rank alone, with no compression at all, already guarantees O(log n) per find.

Stack the two together and the amortized cost per operation drops to O(α(n)), the inverse Ackermann function. Nobody expects you to prove that in an interview, and you shouldn't try. The intuition is enough: a slow find down a tall chain compresses it and speeds up everything after, while rank makes sure the chains rarely get tall to begin with. They cover each other's blind spots. Rank prevents the worst case, compression repairs whatever tall structure sneaks through.

python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))    # Each node is its own root
        self.rank = [0] * n             # Approximate depth of each tree
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

Without union by rank

Union always attaches right to left. Merging {1} into {2} into {3} into {4} creates a chain: 1<-2<-3<-4. Height grows to n.

←2

←3

←4

Worst case: linear chain, find is O(n)

Union splits into three cases, all falling out of that one observation about height. Taller tree wins: hang the shorter one under it and the overall height doesn't budge, because the taller side's depth still dominates. Only when the ranks tie does the result come out strictly taller than either input, and only then do you increment:

python

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        
        if root_x == root_y:
            return False                 # Already in same group
        
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y       # Shorter under taller
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x       # Shorter under taller
        else:
            self.parent[root_y] = root_x       # Same height — pick one
            self.rank[root_x] += 1             # Tree got one level deeper
        
        return True                      # Successfully merged

Time Complexity:

With both path compression and union by rank:
- find: O(α(n)) ≈ O(1) amortized
- union: O(α(n)) ≈ O(1) amortized

α(n) is the inverse Ackermann function. For any practical input size, α(n) ≤ 4.

Count Connected Components

Counting connected components is the problem Union Find was born for. You're handed a list of friendships and asked how many separate friend groups exist. Assume everyone starts as a stranger, so you begin with n groups. Every friendship might merge two groups: if the two people already share a group, nothing moves, and if they don't, one merge fires and the count drops by one.

The code is almost embarrassingly short. Run union on every edge, then count the distinct roots left standing, one per connected component:

python

def count_components(n, edges):
    uf = UnionFind(n)
    
    for u, v in edges:
        uf.union(u, v)               # Merge connected nodes
    
    # Count unique roots = number of components
    return len(set(uf.find(i) for i in range(n)))

Watch the parent array evolve as we process edges for n=5, edges=[[0,1], [1,2], [3,4]]:

Start: parent = [0, 1, 2, 3, 4]. Every node is its own root. 5 components.

union(0, 1): find(0)=0, find(1)=1. Different roots. Attach 1 under 0: parent = [0, 0, 2, 3, 4]. Now find(1) returns 0. 4 components.

union(1, 2): find(1) follows 1->0, returns 0. find(2)=2. Different roots. Attach 2 under 0: parent = [0, 0, 0, 3, 4]. Path compression: if we called find(1), parent[1] already points to 0, just one step. 3 components.

union(3, 4): find(3)=3, find(4)=4. Attach 4 under 3: parent = [0, 0, 0, 3, 3]. 2 components.

Final state: Nodes 0, 1, 2 all trace to root 0. Nodes 3, 4 trace to root 3. Two components. The find call on any node is at most one hop thanks to path compression.

You can also keep the count inside the UnionFind itself: start at n and decrement on each successful union. Either way it's O(E × α(n)). Cycle detection is the same idea read backwards. When find(u) == find(v) already holds before you union, the edge would close a loop, since u and v are in one component and connecting them again just completes a cycle. Grids are the same problem in disguise: flatten 2D coordinates to 1D with row * cols + col, then union adjacent cells that share a value or meet whatever condition the problem sets.

When to Use Union Find vs DFS/BFS

The question that decides it: are edges being added over time, or is the graph fixed?

For a static graph and one query ("are A and B connected?"), reach for DFS or BFS. It's simpler and just as fast, O(V + E) for a single traversal. The moment you have to answer that question repeatedly as edges keep arriving, DFS and BFS fall apart, because each new edge can change connectivity and you'd rebuild the whole traversal every time. Ten thousand edges means ten thousand full traversals, O(E × (V + E)) in total.

Union Find shrugs this off. Each new edge is a single union(), O(α(n)) amortized, so ten thousand edges cost you ten thousand near-constant operations. At any moment, find(a) == find(b) answers the connectivity query, also O(α(n)). Nothing gets rebuilt and nothing gets re-traversed.

Here's what you give up. Union Find tells you WHETHER two nodes are connected, never HOW. It can't hand you the path between them. So the moment a problem wants the shortest path, or nodes visited in BFS order, or a path of length exactly k, Union Find is the wrong tool and you should reach for a traversal. It answers one question: does a route exist. That's all it knows.

Use Union Find when:
- Dynamic connectivity (edges added over time)
- Need to answer many "are X and Y connected?" queries
- Counting/tracking connected components as edges added
- MST algorithms (Kruskal's)
- Redundant edge detection

Use DFS/BFS when:
- Need the actual path between nodes
- Static graph with single traversal
- Level-order or distance information needed
- Visiting all nodes in specific order
- Problems with additional constraints during traversal

Common Applications

Count connected components

Union all edges, return count

Track count in UF structure

Is graph connected?

Union all edges, check count == 1

Single component = connected

Find redundant edge

Union returns false = redundant

Edge between already-connected nodes

Earliest time all connected

Process edges in time order

Return time when count == 1

Accounts merge / synonyms

Union equivalent items

Group items with same root

Kruskal's MST

Sort edges, union if not connected

Skip edges that create cycles

Practice

Start with n components. Each successful union decreases the count by 1.

Try it yourself

Number of Connected Components

Given n nodes labeled from 0 to n-1 and a list of undirected edges, return the number of connected components in the graph.

Examples

Input: n = 5, edges = [[0,1],[1,2],[3,4]]

Output: 2

Components: {0,1,2} and {3,4}

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]

Output: 1

All nodes connected

Number of Connected Components

Click "Run" to execute your code

Test Cases

Input: 5, [[0,1],[1,2],[3,4]]Expected: 2

Input: 5, [[0,1],[1,2],[2,3],[3,4]]Expected: 1

Input: 3, []Expected: 3

Input: 4, [[0,1],[2,3]]Expected: 2

Solution

def solution(nums, target):

left, right = 0, len(nums) - 1

while left <= right:

mid = left + (right - left) // 2

if nums[mid] == target:

return mid

elif nums[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

# Time: O(log n) | Space: O(1)

View Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

Nearly Constant-Time Connectivity

With path compression and union by rank, Union Find answers connectivity in essentially O(1) per operation. When a problem is about grouping elements or tracking components as they merge, this is the structure to reach for.

The template barely fills a screen, and that same handful of lines covers graph connectivity, redundant edge detection, and the dynamic grouping problems stacked on top of them.

Key Takeaways

Union Find answers "same group?" in O(α(n)) ≈ O(1)
Path compression: flatten tree during find
Union by rank: attach smaller tree under larger
Track component count by decrementing on successful union
Use for dynamic connectivity, DFS/BFS for paths

Next: Topological Sort