---
title: 'Disjoint Sets'
source: 'https://academia.sh/en/courses/data-structures/disjoint-sets'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:50+00:00'
license: 'CC BY-SA 4.0'
---

# Disjoint Sets

The dynamic grouping problem, the union-find structure, union by rank, path compression, and its uses.

Suppose the question is whether two computers in a network are connected — directly
or through intermediaries. Connections are added over time and never removed. Two
questions arrive in turn: *"are these two in the same group?"* and *"merge these two
groups."*

This is the problem solved by the **disjoint sets** structure — also known as
**union–find**. Its name comes from the sets having no intersection: every element
belongs to exactly one group.

## Two Operations

| Operation | Meaning |
|---|---|
| `find(x)` | Returns the representative of the group `x` belongs to |
| `union(x, y)` | Merges the groups of the two elements into one |

The "same group" question requires no separate operation: if two elements'
representatives are the same, they are in the same group.

A **representative** is any element of the group; which element it is does not
matter — what matters is that every element in the same group finds the same
representative.

## Forest Representation

The structure keeps every group as a tree; the tree's root is the group's
representative. All the groups together form a **forest**.

The representation is a single array: `parent[x]` holds `x`'s parent node. A root
points to itself.

```
parent:  [0, 0, 1, 3, 3]
          ↑
          0 and 3 are roots (pointing to themselves)

group 1: 0 ← 1 ← 2        group 2: 3 ← 4
```

The `find` operation follows parent links until it reaches the root. `union`
attaches one of two roots to the other.

In this plain form, the structure can degenerate in the worst case: if every union
attaches a root to the end of a long chain, the tree turns into a linked list and
`find` becomes $O(n)$.

## Two Improvements

**Union by rank.** During a union, the smaller tree's root is attached to the larger
one's. This way, depth increases only when two trees of equal size merge; tree height
is bounded by $O(\log n)$. Either the element count or an estimated height (rank) is
used as the size measure. Both give the same bound; the element count is often
preferred because it provides a side benefit — the group size can also be queried.
Once path compression is applied, the estimated height can exceed the actual height —
meaning the measure is used only in the union decision and does not need to be exact.

**Path compression.** As the `find` operation locates the root, it attaches every
node along the way directly to the root. The next query does not retrace the same
path. The operation flattens the structure as a byproduct of the query.

When both are applied together, the total cost of $m$ operations is nearly linear:
the amortized cost per operation is bounded by a function that grows slowly enough to
be treated as constant in practice. The precise statement and proof belong to the
**Advanced Algorithms** course; what is enough for this course is that the two
improvements are used together.

```python
class DisjointSets:
    """Union-find with union by size and path compression."""

    def __init__(self, n: int) -> None:
        self._parent = list(range(n))    # initially, everyone is their own group
        self._size = [1] * n
        self.group_count = n

    def find(self, x: int) -> int:
        root = x
        while self._parent[root] != root:    # climb to the root
            root = self._parent[root]
        while self._parent[x] != root:        # path compression: attach the path to the root
            self._parent[x], x = root, self._parent[x]
        return root

    def union(self, x: int, y: int) -> bool:
        a, b = self.find(x), self.find(y)
        if a == b:
            return False                  # already in the same group
        if self._size[a] < self._size[b]:
            a, b = b, a                   # the larger tree becomes the root
        self._parent[b] = a
        self._size[a] += self._size[b]
        self.group_count -= 1
        return True

    def same_group(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


ds = DisjointSets(6)                      # six elements, 0..5
ds.union(0, 1)
ds.union(1, 2)
ds.union(3, 4)

print(ds.same_group(0, 2))                # True
print(ds.same_group(0, 3))                # False
print(ds.group_count)                     # 3   — {0,1,2}, {3,4}, {5}

print(ds.union(0, 2))                     # False — already together
ds.union(2, 4)
print(ds.same_group(1, 3), ds.group_count)   # True 2
```

The `union` operation returning a logical value is a practical detail: the caller
learns whether a merge actually took place. This information is used directly in the
applications covered in the next section.

## Tracing

To see how the structure flattens, the parent array can be examined step by step:

```python
ds = DisjointSets(5)
ds.union(1, 2)
ds.union(3, 4)
ds.union(2, 4)
print(ds._parent)             # [0, 1, 1, 1, 3]  — 3's root is still indirect

ds.find(4)                    # path compression runs
print(ds._parent)             # [0, 1, 1, 1, 1]  — 4 is now attached directly to the root
```

In the first output, node `4`'s root was found in two steps (`4 → 3 → 1`); after a
single `find` call, the link points directly to the root. Compression is not a
separate maintenance operation — the query itself improves the structure.

## What It Cannot Do

The structure's well-known limit is that **splitting is not supported**. Groups
merge, they do not split. When a connection is removed, the groups must be
recomputed; this means building the structure from scratch.

The second limit is that group members cannot be listed. The structure only answers
the "same group" question; counting or listing a group's elements requires keeping
additional records.

These constraints are not accidental: the structure's speed comes precisely from not
keeping this information.

## Applications

**Connected components.** Which nodes in a graph can reach each other is tracked with
this structure as edges are added. In this course's last topic, the same question
will also be answered with traversal algorithms; disjoint sets are more suitable when
edges arrive as a stream.

**Minimum spanning tree.** The algorithm that sorts edges by weight and selects the
ones that do not form a cycle asks the "does this edge form a cycle" question with
disjoint sets: if the two endpoints are already in the same group, the edge is
skipped. The algorithm itself is covered in the **Algorithms** course.

**Equivalence classes.** Groups formed by accumulating rules of the "these two count
as the same" kind — merging accounts belonging to the same person, matching records
that refer to the same object — are held directly with this structure.

**Grid problems.** Regions formed by merging adjacent cells in a grid (connected
areas in an image, percolation models) are tracked the same way.

Another property of the structure is that its result is **independent of the order**
of operations: no matter what order the same set of unions is applied in, the
resulting groups are the same. Only the internal shape of the trees changes, and this
does not affect the result of any query.

## Cost Table

| Implementation | `find` | `union` |
|---|---|---|
| Plain forest | $O(n)$ | $O(n)$ |
| Union by size | $O(\log n)$ | $O(\log n)$ |
| + path compression | Amortized nearly constant | Amortized nearly constant |

## Summary

- The disjoint-set structure divides elements into non-intersecting groups and offers
  two operations: finding a group's representative and merging two groups.
- Groups are kept as a forest; the root is the group's representative.
- Union by size keeps the height logarithmic by attaching the smaller tree to the
  larger one.
- Path compression flattens the structure during `find` by attaching the nodes along
  the path directly to the root.
- Together, the two give an amortized, nearly constant cost per operation.
- The structure does not support splitting or listing a group's elements; its speed
  comes from not keeping this information.

## Next Step

This topic used a tree representation for groups, but trees themselves were never
defined. The next topic covers trees on their own: terminology, traversal methods,
search trees, the balance problem, and the heap structure that implements a priority
queue.