Fişierul intrare/ieşire:	disjoint.in, disjoint.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Paduri de multimi disjuncte

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 interogari, astfel:

• interogarea 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)
• interogarea 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. 

Date de intrare

Pe prima linie a fisierului de intrare disjoint.in se vor afla 2 numere, N si M, reprezentand numarul de multimi, respectiv numarul de interogari facute asupra lor. Pe urmatoarele M linii se vor afla cate 3 numere, cod, x si y, cod reprezentand tipul interogarii, x si y avand semnificatia din enunt.

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.

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 100 000

Exemplu

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.
O abordare 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:
1. 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.
2. Compresia drumurilor: Atunci cand facem o interogare, dupa ce am aflat in ce multime se afla nodul x, mai parcurgem odata 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.
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.
Nota: log*N (a se citi "log star de N", reprezinta inversa functiei lui Ackermann. Acest log* poate de asemenea fi foarte usor aproximat cu O(1). Aveti aici un tabel cu valorile pe care le ia acesta.

Cum se trimit solutii?