Union-Find (Disjoint Set Union) rastreia uma partição de elementos em conjuntos disjuntos e suporta duas operações quase-O(1): find (em qual conjunto x está?) e union (mesclar dois conjuntos). É excelente em consultas de conectividade.
A ideia
Cada conjunto é uma árvore com uma raiz representativa. Com e , operações rodam em tempo quase constante (Ackermann inverso, α(n)).
