Aka. Disjoint Set Union (DSU). Keeps track of a partition of a set into disjoint subsets.
Used in Kruskal’s algorithm, connected components in a graph, cycle detection in undirected graphs, dynamic connectivity problems.
Operations
Section titled “Operations”Determines which subset a particular element belongs to. This can be used to check if two elements are in the same subset.
Joins two subsets into a single subset. This is used to merge groups.
Implementation
Section titled “Implementation”Typically implemented using two techniques to optimize its operations:
Path Compression
Section titled “Path Compression”During the Find operation, the structure flattens the tree by making every node point directly to the root. This reduces the time complexity of future operations.
Union by Rank
Section titled “Union by Rank”During the Union operation, the smaller tree is attached under the root of the larger tree. This keeps the tree shallow, improving efficiency.