Union-Find Data Structure Explained: Near-Constant Time Connectivity

Union-Find (Disjoint Set Union) is a data structure that tracks connectivity between elements, supporting union and find operations in amortized O(α(n)) time. Two optimizations—union by rank and path compression—keep trees shallow and queries fast. It's widely used in graph algorithms like counting connected components or detecting cycles.