Union-Find (DSU) Mastery

Union-Find is a data structure that tracks elements partitioned into a number of disjoint (non-overlapping) sets. It provides two near-instant operations: Find (which set is this in?) and Union (merge two sets).

1. Path Compression

When you call Find(X), you don't just find the root; you point every node in the path directly to the root for next time. This "flattens" the tree structure, ensuring subsequent searches are O(1).

2. Union by Rank/Size

Always attach the smaller tree to the root of the larger tree. This prevents the tree from becoming a long chain and keeps the height at O(Log N).

3. The Magic Inverse Ackermann Function

With both optimizations, the complexity of Union/Find is α(N), where α is the inverse Ackermann function. For all practical purposes (N < number of atoms in the universe), this is Constant Time O(1).

4. Interview Mastery

Q: "How do you count the number of connected components in a social network using DSU?"

Architect Answer: "You start with every person in their own set. For every 'Friendship' (edge), you call `Union(Person1, Person2)`. At the end, the number of distinct 'Roots' in your DSU structure is exactly the number of isolated island communities in your social network. It is much faster and cleaner than running multiple BFS passes."