Union-Find (or Disjoint Set Union, DSU) is a data structure that tracks elements partitioned into disjoint subsets, supporting rapid merging () and representative finding () operations. Optimized with path compression and union by rank/size, it achieves near-constant amortized time complexity, $O(\alpha(n))$ , making it efficient for Kruskal’s algorithm and dynamic connectivity. [ 1 , 2 , 3 , 4 ] Key Concepts and Operations Find(x): Determines the representative (root) of the set containing element . Union(x, y): Merges the sets containing elements and . MakeSet(x): Initializes a new set containing only element . Structure: Typically implemented as a forest of trees, where each node points to its parent. The root of a tree is its own parent and acts as the representative. [ 4 , 5 , 6 , 7 , 8 ] Optimizations Path Compression: During a operation, makes every node on the path point directly to the root, flattening the tree. Union by Rank/Size: Always attaches the smaller tr...