Data Structures

Disjoint Set Union

The Disjoint Set Union (DSU) data structure is used to maintain a collection of disjoint sets. It provides efficient operations for adding elements, finding the representative of a set, and merging two sets.

Usage

Example

Functions

• constructor(int n): initializes the DSU with n elements
• int find(int x): returns the representative of the set containing x
• bool unite(int x, int y): merges the sets containing x and y and returns true if they belong to different sets. The representative element of the merged sets is the representive element of the larger one before uniting.
• bool connected(int x, int y): returns true if the sets containing x and y are the same