# Disjoint-Set Data Structures

The disjoint-set data structure is a data structure that represents set partitions.

A set partition of a set S is a collection of disjoint subsets of S whose union is S.

Sets are disjoint if and only if they have no elements in common, and the union of a collection of sets is the set obtained by combining the elements of each set. So, when we partition a set, we put all of its elements into a collection of subsets, making sure that none of the subsets share any elements. For example, the set partitions of {1,2,3} are {{1,2,3}}, {{1},{2},{3}}, {{1},{2,3}}, {{1,2},{3}}, and {{1,3},{2}}.

Again, a disjoint-set data structure lets us efficiently model a set partition on a computer. It has two operations defined on it:

1. Union: Replaces two subsets with their union.

2. Find: Locates an element’s subset.

For this reason, disjoint-set data structures are also called “union-find data structures.”

Kruskal’s algorithm uses disjoint-set data structures to find minimum spanning trees.