Dsu

Disjoint-set union (DSU), also known as union-find, is a data structure that maintains a partition of a set into disjoint non-overlapping subsets. It supports two primary operations: finding the representative of the set containing a given element, and merging two sets into a single set. DSU is widely used to track connectivity and components in undirected graphs and in algorithms that require repeated unions and membership queries.

Implementation typically uses two arrays: parent and rank (or size). Each element starts as a singleton set with itself as its own parent. The find operation follows parent pointers to the root representative, often applying path compression to flatten the tree and speed up future finds. The union operation merges the sets containing two elements, attaching the root of one set to the root of the other and updating the rank or size. Union by rank attaches the shorter tree to a taller one; union by size attaches the smaller set to the larger one.

Advanced variants include persistent or rollback DSU for maintaining historical versions, and implementations that encode size information within the same array. The amortized time for each operation is nearly constant, specifically O(alpha(n)), where alpha is the inverse Ackermann function, which grows extremely slowly. Space usage is O(n).

Common applications include computing minimum spanning trees via Kruskal's algorithm, determining connectivity between nodes, and cycle detection in graphs, as well as offline dynamic connectivity problems. DSU is a fundamental data structure in computer science, frequently taught in data structures courses and employed in competitive programming for problems involving dynamic connectivity and partition management.