Disjoint Set Union / Union Find

overview

Summary

Disjoint Set Union (DSU), also called Union-Find, maintains a partition of elements into disjoint sets while supporting fast queries to check if two elements share a set and to merge sets. It uses a parent array to represent forested trees where each tree root is a set representative. With path compression and union by rank or size, operations run in near-constant amortized time. DSU shines in dynamic connectivity, Kruskal's MST, cycle detection, and clustering tasks.