DevPath
Tracks

Union-Find (Disjoint Sets)

Track which items belong to the same group with near-constant-time merge and lookup, using path compression and union by size.

intermediate35 min#union-find#disjoint-set#graphs#connectivity

Prerequisites: Arrays and Dynamic Arrays, Graphs: Representations, BFS and DFS

Why it matters

Many problems boil down to one question asked repeatedly: are these two things in the same group, and can I merge their groups? Friends-of-friends networks, connected regions in an image, grouping accounts that share an email, detecting a cycle while adding edges, and Kruskal's minimum spanning tree all need it. A graph search answers connectivity once in O(n). Union-find answers it after each new edge in nearly constant time, which is what you need when edges arrive over time.

Intuition

Picture a room full of people, each initially standing alone. Every group has a leader. To check whether two people are in the same group, ask each for their leader; if the leaders match, they are together. To merge two groups, make one leader report to the other.

Store this as a forest: each item points to a parent, and a root is its own parent. "Find" climbs to the root. "Union" links one root under another.

How it works

Start with parent[i] = i for every item. Two operations:

  • find(x): follow parent pointers until you reach a root (parent[r] == r).
  • union(a, b): find both roots; if different, link one under the other.

Here is the demo from the code below as a forest. Each arrow points from an item to its parent, and green items are roots.

0123456
Seven items, each its own root (green). parent = [0, 1, 2, 3, 4, 5, 6]. Components: 7.
step 1 / 6

Each tree in the forest is one set; the root is its leader. Merging two sets only moves one arrow, and a redundant union changes nothing.

Used naively, a chain of unions can build a long skinny tree where find costs O(n). Two small tricks fix that.

Union by size (or rank): always attach the smaller tree under the larger one. A tree's depth then only increases when it at least doubles in size, so depth is at most log n.

Path compression: while climbing in find, make nodes point closer to the root. The code below uses path halving: each visited node jumps to its grandparent. Later finds on those nodes are shorter.

before:  4 -> 3 -> 2 -> 1 -> 0 (root)     find(4) walks 4 steps
after find(4) with path halving:
         4 -> 2 -> 0,   3 -> 2,   1 -> 0   later finds are shorter

Here is path halving running on that chain, with the parent array underneath.

0
0
0
1
1
2
2
3
3
4
x
A skinny chain 4 -> 3 -> 2 -> 1 -> 0. The array shows each item's parent: parent = [0, 0, 1, 2, 3]. find(4) starts at x = 4.
step 1 / 4

Cell i holds parent[i]. Every visited node jumps to its grandparent, so the next find on any of these nodes is shorter.

With both tricks, the amortized cost per operation is O(alpha(n)), where alpha is the inverse Ackermann function. It grows so slowly that it is at most 4 for any input that fits in the universe. In practice, treat it as constant.

Tracking the count of components is easy: start with n and subtract one every time a union actually merges two different roots. A union that finds the roots already equal is a redundant edge, which is exactly how you detect a cycle in an undirected graph.

OperationTimeNotes
make-set (initialize n items)O(n)parent[i] = i
findO(alpha(n))Amortized, with compression and size
unionO(alpha(n))Two finds plus a link
SpaceO(n)Parent and size arrays
Without optimizationsO(n) per opDegenerate chain

Code: a reusable UnionFind

The demo adds five edges to a graph of 7 nodes. Edge (2, 0) closes a cycle with the first two edges, and (5, 5) is a self-loop, so both are redundant.

0123456
The demo graph. Colours are the connected components that union-find reports: three nodes in one, two in another, and nodes 5 and 6 alone, so 4 components. Edge (2, 0) closes the triangle 0, 1, 2, which is why it was redundant.
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # every node starts as its own root
        self.size = [1] * n
        self.components = n
 
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # attach smaller tree under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True
 
edges = [(0, 1), (1, 2), (3, 4), (2, 0), (5, 5)]
uf = UnionFind(7)
redundant = [e for e in edges if not uf.union(*e)]
print(uf.components)
print(len(redundant), *redundant[0])
print(str(uf.find(0) == uf.find(2)).lower(), str(uf.find(0) == uf.find(3)).lower())

Both versions print three lines: 4 (components: one of 0,1,2; one of 3,4; and singletons 5 and 6), 2 2 0 (two redundant edges, the first being 2 0), and true false (0 and 2 are connected, 0 and 3 are not).

Common pitfalls

  • Unioning the items instead of the roots: always call find first and link the roots. Linking arbitrary nodes can break the tree.
  • Forgetting path compression: the code stays correct but loses its speed guarantee.
  • Recursive find on huge inputs: a recursive find can overflow the stack on a deep tree in Python. The iterative loop used here avoids that.
  • Mapping non-integer items: union-find indexes arrays. Map strings or emails to integer ids first using a dictionary or Map.
  • Reading parent[x] as the root: after unions, parent[x] may not be the root. Always call find(x).

Practice

Number of provinces easy

Hint

Each connected pair of cities is a union. Count components at the end.

Show solution

Create a UnionFind(n). For every pair i, j marked connected in the matrix, call union(i, j). The answer is components. O(n^2 * alpha(n)) because the matrix has n^2 entries.

Redundant connection medium

Hint

Process edges in order. Which edge joins two nodes that are already connected?

Show solution

Union each edge as it comes. The first edge for which union returns false closes a cycle, so return it. The graph started as a tree plus one extra edge, so that edge is the answer. O(n * alpha(n)).

Accounts merge medium

Hint

Treat each email as a node. Accounts sharing any email belong together.

Show solution

Map each distinct email to an integer id. For each account, union the id of its first email with every other email in that account. Then group emails by find(id), attach the owner name, and sort each group. Total near O(E * alpha) plus the sort.

Minimum spanning tree (Kruskal) hard

Hint

Sort edges by weight. Add an edge only if it connects two different components.

Show solution

Sort edges by weight ascending. For each edge, if union(u, v) returns true, add its weight to the total; otherwise skip it (it would form a cycle). Stop after n - 1 accepted edges. The sort dominates: O(E log E). This is correct by the greedy cut property.

Interview questions

  1. What two optimizations make union-find fast, and why? Union by size keeps trees shallow; path compression flattens them during finds. Together they give near-constant amortized time.
  2. How do you detect a cycle in an undirected graph with union-find? Union the endpoints of each edge; if they already share a root, that edge closes a cycle.
  3. When would you prefer BFS or DFS to union-find? For a one-off connectivity or path query on a fixed graph. Union-find shines when connections are added incrementally and you query often, and it cannot give you the actual path.
  4. Can it handle deleting an edge? Not directly; it is a merge-only structure.

Interviewers look for: iterative find with compression, union by size or rank, a component counter, and using the boolean result of union to spot redundant edges.

Quick check

While adding edges one by one, union(a, b) finds that a and b already have the same root. What does this mean?

Finished this lesson?

Further resources

Related lessons