 Disjoint-set data structure

A disjoint-set data structure maintains a partition of a set. Its find operation returns a representative, equal for two elements exactly when they belong to the same block; its union operation merges two blocks. Kruskal's algorithm uses it to track connected components of a graph.

Start with a singleton set for every stored set element. Each disjoint-set find operation returns a disjoint-set representative; a disjoint-set union operation merges the containing blocks of a set partition. The interface does not split a block of a set partition or delete a member.^[ref]

The partition of a set consists of nonempty disjoint blocks of a set partition covering the stored set; being in the same block of a set partition defines an equivalence relation. A disjoint-set representative names a whole block of a set partition, without requiring a list of its members.

A Disjoint-set data structure, also known as a union-find data structure, is a data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets. It supports two primary operations: 1. **Find**: This operation determines which subset a particular element is in. It can be used to check if two elements are in the same subset. 2. **Union**: This operation merges two subsets into a single subset.