== include(page="template/taskheader" task_id="disjoint") ==
Poveste şi cerinţă...
Se dau $N$ multimi de numere, initial fiecare multime $i$ continand un singur element, mai exact elementul $i$. Asupra acestor multimi se pot face $2$ tipuri de operatii, astfel:
* operatia de tipul $1$: se dau doua numere naturale $x$ si $y$, intre $1$ si $N$. Se cere sa reuneasca multimile in care se afla elementul x, respectiv elementul y (se garanteaza ca $x$ si $y$ nu se vor afla in aceeasi multime)
* operatia de tipul $2$: se dau doua numere naturale $x$ si $y$, intre $1$ si $N$. Se cere sa afiseze $DA$ daca cele $2$ elemente se afla in aceeasi multime, respectiv $NU$ in caz contrar.
h2. Date de intrare
Fişierul de intrare $disjoint.in$ ...
Pe prima linie a fisierului de intrare $disjoint.in$ se vor afla $2$ numere, $N$ si $M$, reprezentand numarul de multimi, respectiv numarul de operatii efectuate. Pe urmatoarele $M$ linii se vor afla cate $3$ numere, $cod$, $x$ si $y$, $cod$ reprezentand tipul operatiei, iar $x$ si $y$ avand semnificatia din enunt.
h2. Date de ieşire
În fişierul de ieşire $disjoint.out$ ...
In fisierul de iesire $disjoint.out$ se vor afisa mai multe linii, fiecare linie continand $DA$ sau $NU$, reprezentand raspunsul la interogarea corespunzatoare din fisierul de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100 000$
h2. Exemplu
table(example). |_. disjoint.in |_. disjoint.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 6
1 1 2
1 3 4
2 1 3
2 1 2
1 1 3
2 1 4
| NU
DA
DA
|
h3. Explicaţie
...
h2. Indicatii de rezolvare
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.
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.
* _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.
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") ==
