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. $x$ si $y$, 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. $x$ si $y$, se cere sa afiseze "DA" daca cele $2$ elemente se afla in aceeasi multime, respectiv "NU" in caz contrar.

* 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

h2. Date de ieşire

In fisierul de iesire $disjoint.out$ se vor afisa mai multe linii, fiecare linie continand $"DA"$ sau $"NU"$ reprezentand raspunsul la interogarea respectiva.

In fisierul de iesire $disjoint.out$ se vor afisa mai multe linii, fiecare linie continand $DA$ sau $NU$ reprezentand raspunsul la interogarea respectiva.

h2. Restricţii

h2. Indicatii de rezolvare

Problema se poate rezolva reprezentand multimile ca pe niste liste inlatuite. Cand va trebui sa verificam daca $2$ elemente se afla in aceeasi multime pur si simplu 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 pur si simplu luam elementul de sfarsit al primei multimi si il conectam de inceputul celeilalte liste. Aceasta abordare are complexitate $O(N)$ pentru o operatie de tip $2$ si $O(1)$ pentru o operatie de tipul $2$.

Problema se poate rezolva reprezentand multimile ca pe niste 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 complexitate $O(N)$ pentru o operatie de tip $2$ si $O(1)$ pentru o operatie de tipul $2$.

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 intre ele, pur si simplu aflam radacinile celor $2$ arbori si le unim.
Asupra acestei abordari putem aplica insa $2$ euristici care scad foarte mult timpul de executie: