Quickly perform Disjoint Set Union (DSU) operations and visualize the results. Our online calculator helps you understand the find and union operations, essential for graph algorithms, network connectivity, and other data structure optimizations. Ideal for students and developers learning about efficient set management.
Formula:
The Disjoint Set Union (DSU) data structure, also known as Union-Find, manages a collection of disjoint sets. Its core operations are:
find(x): Determines which set an elementxbelongs to. It returns the representative (or root) of that set. With path compression, this operation becomes very efficient.union(x, y): Merges the sets containing elementsxandyinto a single set. This typically uses a heuristic like union by rank or union by size to maintain tree balance, ensuring efficiency.
The state of the DSU is often represented by a parent array, where parent[i] stores the parent of element i.