14. Union-Find (DSU) + Minimum Spanning Trees

Union-Find / Disjoint Set Union (DSU) is a useful data structure when you need to repeatedly determine whether two nodes belong to the same connected group, and merge those groups together. It offers two core operations: find(x), which determines which group a particular node x belongs to, and union(a, b), which merges the groups containing nodes a and b.

The basic implementation of DSU consists of a parent array that initially assigns each node to its own group, a find() method to locate the group for a given node, and a union() method to concatenate two groups.

A key optimization technique used in DSU is path compression, which can be achieved by setting self.parent[x] = self.find(self.parent[x]) during the find() operation. This flattens the structure of the tree, making future find() operations faster. Another optimization is union by size or rank, which involves attaching the smaller tree to the larger tree when performing a union operation.

DSU is particularly useful in scenarios involving connected components, merging groups, determining if two nodes are connected, connecting two nodes, detecting a redundant edge, finding the number of provinces, or checking if multiple accounts belong to the same person. Furthermore, it can be applied to solve the minimum spanning tree problem.

An example of using DSU for cycle detection is demonstrated by a graph with edges 1-2, 2-3, and 3-1. When processing the edge 3-1, the find() operation reveals that both nodes are already connected, indicating the presence of a cycle. The has_cycle() function implements this logic, returning True if a cycle is detected, or False otherwise. The complexity of the algorithm is O(E α(V)), which is practically equivalent to O(E), where α(V) denotes the inverse Ackermann function.