Union-Find (Disjoint Set Union) houdt een partitie van elementen in disjuncte verzamelingen bij en ondersteunt twee bijna-O(1) operaties: find (in welke verzameling zit x?) en union (voeg twee verzamelingen samen). Het blinkt uit bij connectiviteitsvragen.
Het idee
Elke verzameling is een boom met een representatieve wortel. Met en draaien operaties in bijna constante tijd (inverse Ackermann, α(n)).
