Intro

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 $O(n)$.

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 $x$'s tree (its component ID)
• Union(x, y): merge the trees containing $x$ and $y$

With path compression and union by rank, both operations are nearly $O(1)$. particularly, $O(\alpha(n))$ where $\alpha$ 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.