Skip to main content
ProgrammersOS
Sign In
Data Structures•Last Updated : 23 Oct 2026
~45 min read

Union-Find (Disjoint Sets)

Track which items belong together as groups merge over time. Build the disjoint-set forest, see why path compression and union by size make it nearly constant time, and apply it to connectivity, cycle detection and minimum spanning trees.

Who is connected to whom, as the network grows

A social network adds friendships one at a time. After each new link you may need to answer: are Alice and Zoe in the same circle of friends, directly or through others? A computer network adds cables and asks whether two machines can reach each other. A photo editor merges adjacent pixels of the same colour into regions.

You could answer each question by running a graph search from scratch, but that costs O(V + E) per query, and the graph keeps changing. What you actually want is a structure that remembers the groups and supports two operations: union, which merges two groups when a new connection appears, and find, which tells you which group an element belongs to. Two elements are connected exactly when find returns the same answer for both. The structure that does this, astonishingly fast, is union-find, also called a disjoint-set union (DSU).

Definition: Disjoint-set (union-find)

A structure that maintains a partition of elements into non-overlapping groups. find(x) returns a representative of x's group; union(a, b) merges the groups of a and b. Two elements share a group exactly when their representatives are equal.

The idea: a forest of upside-down trees

Represent each group as a tree in which every element points to a parent, and the root of the tree is the group's representative, pointing to itself. To find an element's group, follow parent links until you reach a root. To union two groups, find both roots and make one root the parent of the other. Merging is just changing a single pointer.

That is the whole structure: an array parent where parent[i] is i's parent, initially parent[i] = i (everyone alone). It is a graph algorithm that needs no graph, only an array.

But the naive version has a trap. Merge carelessly and the trees become long chains, so find walks a long path. Two small ideas fix it.

Two groups merging
before:      1          5            after:       1
           / \        / \                      /|\ \
          2   3      6   7                    2 3 5  (5 now child of 1)
                                                  / \
 parent = [-, 1, 1, 1, ?, 5, 5, 5]               6   7

find(7): 7 -> 5 -> 1   (root).   find(2): 2 -> 1.
union(3, 6): find both roots (1 and 5) and hang the smaller tree under the larger.

Two optimisations that change everything

Union by size (or by rank): when merging, attach the smaller tree beneath the larger one. A node's depth only increases when its tree is absorbed into one at least as big, so depths can double at most log2 n times. Trees stay shallow, and find costs O(log n).

Path compression: while finding the root, make every node you pass through point directly at the root. The first find on a long chain pays for the walk, but afterwards every node on that chain is one hop from the root. The structure heals itself as it is used.

Together, the two give an amortised cost per operation of O(alpha(n)), where alpha is the inverse Ackermann function, which grows so slowly that it is below 5 for any input that could ever fit in a computer. In practice, call it constant time. Either optimisation alone is also very good, and path compression alone gives O(log n) amortised.

PythonUnion-find with size tracking and path compression
1class DSU:
2    def __init__(self, n):
3        self.parent = list(range(n))
4        self.size = [1] * n
5        self.groups = n
6 
7    def find(self, x):
8        root = x
9        while self.parent[root] != root:
10            root = self.parent[root]
11        while self.parent[x] != root:            # path compression
12            self.parent[x], x = root, self.parent[x]
13        return root
14 
15    def union(self, a, b):
16        ra, rb = self.find(a), self.find(b)
17        if ra == rb:
18            return False                         # already together
19        if self.size[ra] < self.size[rb]:        # union by size
20            ra, rb = rb, ra
21        self.parent[rb] = ra
22        self.size[ra] += self.size[rb]
23        self.groups -= 1
24        return True
25 
26dsu = DSU(8)
27for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (6, 7), (5, 7)]:
28    merged = dsu.union(a, b)
29    print("union", (a, b), "merged" if merged else "already connected", "| groups:", dsu.groups)
30 
31print("0 and 2 connected:", dsu.find(0) == dsu.find(2))
32print("0 and 4 connected:", dsu.find(0) == dsu.find(4))
33print("size of group containing 4:", dsu.size[dsu.find(4)])
34print("redundant union(0, 3):", dsu.union(0, 3))
Output
union (0, 1) merged | groups: 7
union (2, 3) merged | groups: 6
union (1, 3) merged | groups: 5
union (4, 5) merged | groups: 4
union (6, 7) merged | groups: 3
union (5, 7) merged | groups: 2
0 and 2 connected: True
0 and 4 connected: False
size of group containing 4: 4
redundant union(0, 3): False

Seeing path compression work

It is worth watching the effect rather than trusting the claim. The next experiment builds the worst case on purpose: a chain of 1,000 elements in which each points to the next, so the root is 999 hops from element 0. The first find walks all that way, but along the way it re-points every node to the root. The second find is a single hop.

PythonA chain flattened by one find
1n = 1000
2parent = list(range(1, n)) + [n - 1]     # 0 -> 1 -> 2 -> ... -> 999 (root)
3 
4def find(x, compress):
5    hops, root = 0, x
6    while parent[root] != root:
7        root = parent[root]
8        hops += 1
9    if compress:
10        while parent[x] != root:
11            parent[x], x = root, parent[x]
12    return root, hops
13 
14print("first find(0), no compression:  ", find(0, False)[1], "hops")
15print("second find(0), no compression: ", find(0, False)[1], "hops")
16print("first find(0), with compression:", find(0, True)[1], "hops")
17print("second find(0), with compression:", find(0, True)[1], "hops")
18print("find(500) afterwards:", find(500, True)[1], "hop")
Output
first find(0), no compression:   999 hops
second find(0), no compression:  999 hops
first find(0), with compression: 999 hops
second find(0), with compression: 1 hops
find(500) afterwards: 1 hop

What union-find is used for

Dynamic connectivity. Add edges one at a time and ask whether two vertices are connected, with near-constant cost per operation. This is the case where DSU beats re-running BFS.

Counting components. Start with n groups; every successful union reduces the count by one.

Cycle detection in undirected graphs. When an edge joins two vertices that are already in the same group, adding it would create a cycle.

Kruskal's minimum spanning tree. Sort edges by weight and take each edge only if its endpoints are in different groups. The union operation makes that test and the merge in one go. The example below builds the cheapest network that connects every city.

DSU does not support splitting a group or deleting an edge. If connections disappear as well as appear, you need a different approach.

PythonKruskal's minimum spanning tree with union-find
1class DSU:
2    def __init__(self, items):
3        self.parent = {x: x for x in items}
4 
5    def find(self, x):
6        while self.parent[x] != x:
7            self.parent[x] = self.parent[self.parent[x]]     # path halving
8            x = self.parent[x]
9        return x
10 
11    def union(self, a, b):
12        ra, rb = self.find(a), self.find(b)
13        if ra == rb:
14            return False
15        self.parent[rb] = ra
16        return True
17 
18cables = [("Oslo", "Bergen", 7), ("Oslo", "Trondheim", 5), ("Bergen", "Trondheim", 8),
19          ("Bergen", "Stavanger", 4), ("Trondheim", "Tromso", 9), ("Stavanger", "Oslo", 6),
20          ("Tromso", "Oslo", 12)]
21cities = {c for a, b, _ in cables for c in (a, b)}
22 
23dsu = DSU(cities)
24total = 0
25for a, b, cost in sorted(cables, key=lambda e: e[2]):
26    if dsu.union(a, b):
27        print("build", a, "-", b, "cost", cost)
28        total += cost
29    else:
30        print("skip ", a, "-", b, "cost", cost, "(would form a cycle)")
31print("total cost:", total)
Output
build Bergen - Stavanger cost 4
build Oslo - Trondheim cost 5
build Stavanger - Oslo cost 6
skip  Oslo - Bergen cost 7 (would form a cycle)
skip  Bergen - Trondheim cost 8 (would form a cycle)
build Trondheim - Tromso cost 9
skip  Tromso - Oslo cost 12 (would form a cycle)
total cost: 24

Common slips

Comparing parents instead of roots. parent[a] == parent[b] is wrong whenever the trees are deeper than one level. Always compare find(a) and find(b).

Forgetting that union takes roots. Setting parent[a] = b on non-roots disconnects a whole subtree from its group in a confusing way. Union the roots.

Using recursion for find on huge inputs. A recursive find on a deep chain overflows the stack. The loop version shown above is safer.

Reading sizes from the wrong node. After union, only the new root holds the correct group size. Look it up through find.

Trying to delete. The structure only merges. For "disconnect" queries, process the operations in reverse order (turning deletions into additions) or use a different structure.

Tip

When the elements are not 0..n-1 (names, coordinates, strings), use a dict for parent, and for grids map (row, col) to row * width + col.

Check your understanding

These questions focus on what each part of the structure is for.

Suggested Quiz
Question 1 of 4

After a series of unions, how do you test whether elements a and b are in the same group?

Quick Syntax & Reference Sheet

Concept / RuleSyntax / Usage
find with compressionwhile parent[x] != x: parent[x] = parent[parent[x]] x = parent[x]
union by sizeattach the smaller root under the larger; size[big] += size[small]
Connected testfind(a) == find(b)
Componentsstart with n; subtract 1 for each union that returns True

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Comparing parent[a] and parent[b] instead of roots

Why it happens: Elements in the same group can have different parents.

Correction: Always call find before comparing.
✕ Mistake 2:

Linking non-root nodes in union

Why it happens: Hanging a node (rather than its root) under another breaks the original group.

Correction: Find both roots first, then link root to root.
✕ Mistake 3:

Expecting to split groups

Why it happens: Union-find only merges.

Correction: Process deletions offline in reverse, or choose a different data structure.

Frequently Asked Questions

How fast is union-find really?

With union by size or rank plus path compression, each operation takes amortised O(alpha(n)) time, where alpha is the inverse Ackermann function, below 5 for any realistic n. It is effectively constant.

When should I use union-find instead of DFS or BFS?

When connections arrive over time and you must answer connectivity queries between additions. For a single static graph, one traversal is just as good.
Next: Database Indexes and Query Plans →
Article Tags:#Union-Find#Disjoint Set#Path Compression#Connected Components#Kruskal#Cycle Detection
Previous TopicTries (Prefix Trees)
Next TopicDatabase Indexes and Query Plans
Was this lesson clear and helpful?

Discussion (0)

Sign in to ask questions and reply.
Loading discussion

Related discussions

Discuss in community