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.
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.
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.
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.