Union-Find Explained: The Data Structure That Makes Connectivity Queries Near-Instant

Union-Find, also known as Disjoint Set Union (DSU), is a data structure designed to efficiently track and query connected components without re-exploring the entire graph each time. It works on two core ideas: each element begins in its own set, and a union operation merges two sets when a connection is discovered. Two key optimizations — union by rank and path compression — keep the internal tree shallow and flat, reducing the cost per operation to an amortized near-constant time known as inverse Ackermann complexity. This makes Union-Find far more efficient than running a BFS or DFS for every connectivity query, which can cost O(V + E) per call. The structure is particularly useful for problems like counting connected islands or determining whether two people belong to the same social network.