Union Find

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

Find

Determines which subset a particular element belongs to. This can be used to check if two elements are in the same subset.

Union

Joins two subsets into a single subset. This is used to merge groups.

Implementation

Typically implemented using two techniques to optimize its operations:

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

During the Union operation, the smaller tree is attached under the root of the larger tree. This keeps the tree shallow, improving efficiency.