Consider this problem: given a stream of edges being added to a graph, how do you efficiently check if two nodes are connected? DFS/BFS from scratch for each query is .
With potentially millions of queries, that's too slow. Union-Find solves this. It maintains a forest where each tree represents a connected component.
Two operations: - Find(x): return the root of 's tree (its component ID) - Union(x, y): merge the trees containing and With path compression and union by rank, both operations are nearly . particularly, where is the inverse Ackermann function, effectively constant for all practical purposes. Union-Find appears in Kruskal's algorithm, cycle detection, connected components, and many graph problems.