De ce contează?
Într-o clasă, prietenii se string în găști. Dacă Ana e prietenă cu Bogdan și Bogdan cu Carla, atunci Ana, Bogdan și Carla sunt în aceeași gașcă, chiar dacă Ana și Carla nu s-au cunoscut direct. Când două găști se împrietenesc, ele fuzionează într-una singură. Întrebarea pe care vrei să o pui repede, de oricâte ori: „Aceștia doi sunt în aceeași gașcă?" Union-Find e structura care răspunde aproape instantaneu, oricât de des fuzionează grupurile.
Intuiția
Ai mulțimi disjuncte (găști) care doar se unesc, niciodată nu se sparg. Vrei două
operații rapide: union(a, b) — contopește gașca lui a cu a lui b — și
find(x) — spune-mi „eticheta" găștii din care face parte x. Dacă
find(a) == find(b), sunt în aceeași gașcă. Trucul e cum alegi eticheta: nu o
ții lipită de fiecare om, ci alegi un reprezentant per gașcă și toți ceilalți
arată spre el.
Reprezentantul e rădăcina unui arbore: fiecare membru arată spre rădăcină,
direct sau printr-un lanț de părinți. Două optimizări independente —
compresia căii (la find) și unirea după rang (la union) — țin arborii atât
de scunzi încât ambele operații costă, amortizat, practic O(1).