Union-Find

The union-find data structure [3] represents disjoint sets. You can merge two sets together (union), and you can look up which set a member is in (find). When implemented correctly for $n$ elements, union and find take on average $O(\alpha(n))$ time, with $\alpha(n)$ the inverse Ackermann function, which is “practically $O(1)$.”

The basic idea is that for each node we store a representative, and to find the set a node belongs to, we follow the chain of representatives until we get to a node who's his own representative, and that node is the name of the set.

There are two things to remember when implementing it in order to get the $\alpha(n)$ runtimes.



Subsections