Union Find is a fundamental data structure used to manage disjoint sets efficiently. It tracks elements that are partitioned into non-overlapping subsets. The structure provides two main operations: Find, which returns the representative of a set containing an element, and Union, which merges two sets together.
Union Find is typically implemented using an array where each element stores the index of its parent. Root elements point to themselves, forming the representative of each set. This array representation efficiently encodes tree structures where each tree represents a disjoint set.
The Find operation traces parent links from an element up to the root. Starting at the target element, it follows parent pointers until it reaches a node that points to itself, which is the root and representative of the set. The time complexity depends on the height of the tree.
The Union operation merges two disjoint sets by connecting their root nodes. First, we find the root of each element using the Find operation. Then we make one root the parent of the other. An important optimization is union by rank, where we attach the smaller tree to the larger one to keep trees balanced.
To summarize what we have learned: Union Find is a powerful data structure for managing disjoint sets. The Find operation efficiently locates set representatives, while Union merges sets together. With optimizations like path compression and union by rank, both operations achieve nearly constant time complexity. This makes Union Find essential for graph algorithms and connectivity problems.