Paduri de multimi disjuncte

Păduri de mulțimi disjuncte

Problema se poate rezolva reprezentand multimile ca liste inlatuite. Cand va trebui sa verificam daca $2$ elemente se afla in aceeasi multime luam fiecare element si parcurgem lista lui pana ajungem la sfarsit. Daca pentru ambele noduri am ajuns la acelasi element atunci ele se afla in aceeasi multime, altfel nu. Cand vrem sa unim $2$ multimi alegem elementul de sfarsit al primei multimi si il conectam la inceputul celeilalte liste. Aceasta abordare are complexitatea $O(N)$ pe operatie si se dovedeste ineficienta.

Abordarea optima este aceea de a reprezenta fiecare multime ca pe un arbore cu radacina. Astfel pentru fiecare operatie de tip $2$ parcurgem arborele in sus din ambele elemente si daca la sfarsit ajungem in aceeasi radacina atunci elementele noastre se afla in aceeasi multime. Atunci cand vrem sa unim $2$ multimi determinam radacinile celor $2$ arbori si le conectam printr-o muchie.

O abordare eficienta este aceea de a reprezenta fiecare multime ca pe un arbore cu radacina. Astfel pentru fiecare operatie de tip $2$ parcurgem arborele in sus din ambele elemente si daca la sfarsit ajungem in aceeasi radacina atunci elementele noastre se afla in aceeasi multime. Atunci cand vrem sa unim $2$ multimi determinam radacinile celor $2$ arbori si le conectam printr-o muchie.

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.

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.

h2. Aplicatii
 
* 'Bile':problema/bile
* 'Mexc':problema/mexc
* 'Curcubeu':problema/curcubeu
* 'Desen':problema/desen
* 'Jstc':problema/jstc
* 'Secvmax':problema/secvmax
* "Walls":http://acm.sgu.ru/problem.php?contest=0&problem=174
 
* "Towers":http://acm.sgu.ru/problem.php?contest=0&problem=263
 

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

3449