Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-11-25 22:22:15.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| 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
| disjoint.in | disjoint.out |
|---|---|
| 3 6 1 1 2 1 3 4 2 1 3 2 1 2 1 1 3 2 1 4 | NU DA DA |
Explicaţie
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici
