Union-Find (Disjoint Set Union)

Union-Find (Disjoint Set Union) tracks a partition of elements into groups and answers 'are these two connected?' in near-constant amortized time using path compression and union by rank. Interviews probe it because the naive alternative (re-running DFS or BFS per query) is too slow under repeated merges, and DSU is the right tool for dynamic connectivity, Kruskal's MST, and grouping problems where edges arrive over time.