union-find
The union-find algorithm, also known as disjoint-set, is a data structure that efficiently manages a collection of non-overlapping sets. It supports two primary operations: union, which merges two sets, and find, which identifies the set containing a specific element. This structure is particularly useful in scenarios like network connectivity and clustering.
Union-find employs techniques like path compression and union by rank to optimize its operations. Path compression flattens the structure of the tree whenever find is called, making future queries faster. Union by rank ensures that smaller trees are always added under larger trees, maintaining a balanced structure for efficiency.