Asupra acestei abordari putem aplica insa $2$ euristici care scad foarte mult timpul de executie:
* _Reuniunea dupa rang_: Pentru fiecare multime tinem minte inaltimea arborelui care reprezinta acea multime si atunci cand vrem sa unim $2$ arbori, il unim pe cel mai mic de cel mai mare.

* _Compresia drumurilor_: Atunci cand facem o interogare, dupa ce am aflat in ce multime se afla nodul $x$, mai parcurgem o data drumul de la $x$ la radacina si unim toate nodurile direct de radacina. Astfel data viitoare cand vom avea o interogare pentru vreo unul din acele noduri vom ajunge din prima la radacina. *Atentie*, e posibil ca atunci cand facem compresia drumurilor, inaltimea arborelui se modifica, insa nu actualizam rangul, in cazul in care folosim si prima euristica. In acest caz acel rang va deveni practic o limita superioara a inaltimii arborelui.

* _Compresia drumurilor_: Atunci cand facem o interogare, dupa ce am aflat in ce multime se afla nodul $x$, mai parcurgem o data drumul de la $x$ la radacina si unim toate nodurile direct de radacina. Astfel data viitoare cand vom avea o interogare pentru unul din aceste noduri vom ajunge intr-un singur pas la radacina. Este posibil ca atunci cand facem compresia drumurilor inaltimea arborelui sa se modifice, insa nu actualizam rangul (in cazul in care este folosita si prima euristica). In acest caz, acel rang va deveni practic o limita superioara a inaltimii arborelui.

Aceste $2$ euristici duc complexitatea finala la $O(log*N)$ pentru o operatie de tipul $2$ si $O(1)$ pentru o operatie de tipul $1$. $log*N$ ("log star de $N$"), reprezinta inversa "functiei lui Ackermann":http://en.wikipedia.org/wiki/Ackermann_function si poate fi aproximat cu $O(1)$. "Aici":http://en.wikipedia.org/wiki/Iterated_logarithm se gaseste un tabel cu valorile pe care le ia acesta.
O sursa de 100 de puncte pe aceasta idee se gaseste 'aici':job_detail/226533?action=view-source. De asemenea puteti gasi informatii utile despre acest subiect si pe "Wikipedia":http://en.wikipedia.org/wiki/Disjoint_set_data_structure.

== include(page="template/taskfooter" task_id="disjoint") ==