Disjoint Sets

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.

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:

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.