disjointset

Disjoint-set, also called a disjoint-set data structure or Union-Find, is a data structure for maintaining a partition of a set into non-overlapping subsets. It supports two primary operations: find and union. make-set(x) creates a singleton set {x}. find(x) returns the representative of the set containing x, while union(x, y) merges the two sets that contain x and y.

Implementation details: typically uses a forest of trees, where each node has a parent pointer; the root is the representative. To merge efficiently, union by rank or union by size attaches the smaller tree to the root of the larger tree. Find is optimized with path compression, which flattens the tree by making each visited node point directly to the root during the search.

Complexity: with both path compression and union by rank, the amortized time per operation is nearly constant, O(alpha(n)), where alpha is the inverse Ackermann function, which grows extremely slowly. Memory usage is O(n) for n elements.

Applications: Kruskal's algorithm for minimum spanning trees uses DSU to test whether adding an edge connects two components; determining connected components in undirected graphs; network connectivity; image processing tasks; percolation modeling; and various clustering and equivalence problems.

Variants and limitations: DSU supports only union and find; it does not efficiently support deletions or arbitrary splits of sets without additional data structures. Some variants maintain additional information per set, such as size, sum, or other attributes.