Disjoint Set

A disjoint set is a collection of groups where no element belongs to more than one group.

It is a useful model when an algorithm needs to track which items are connected or grouped together.

Core Idea

Each element belongs to exactly one set. Two operations matter most: checking which set an element belongs to, and merging two sets.

The data structure commonly used for this model is Union-Find.

Usage Contract

A disjoint-set model assumes each element belongs to exactly one group at a time.

The model answers group-membership questions such as whether two elements are already connected. It does not answer which path connects them or how far apart they are.

Python Example

groups = [
    {0, 1, 2},
    {3, 4},
    {5},
]

This is the concept: separate non-overlapping groups. Efficient algorithms do not usually store groups as literal Python sets like this.

Step-by-Step Example

Start with five elements:

{0}, {1}, {2}, {3}, {4}

After merging 0 and 1:

{0, 1}, {2}, {3}, {4}

After merging 3 and 4:

{0, 1}, {2}, {3, 4}

The sets are disjoint because no element appears in more than one group.

What Questions It Answers

Disjoint-set structure answers questions such as:

• Are a and b already in the same group?
• What happens if these two groups merge?
• Would adding this edge connect two separate components or create a cycle?

It does not answer which path connects two elements.

Common Confusions

“Disjoint set” describes the grouping model. “Union-Find” usually refers to the efficient data structure that supports the model.

Disjoint sets are about membership in components, not about finding paths through a graph.

Another common mistake is storing actual Python sets and merging them repeatedly for large inputs. That can be much slower than Union-Find.

When To Use It

Use disjoint-set thinking when items start separate and the algorithm repeatedly merges groups or asks whether two items are already in the same group.

Do not use it when the problem needs traversal order, shortest paths, or the actual route between elements.

The Main Point

Disjoint sets track group membership under merges. They answer connectivity membership, not paths or distances.