Fişierul intrare/ieşire:disjoint.in, disjoint.outSursăInfoarena
AutorTeorieAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.25 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Disjoint

Se dau N mulţimi de numere, iniţial fiecare mulţime i conţinând un singur element, mai exact elementul i. Asupra acestor mulţimi se pot face 2 tipuri de operaţii, astfel:

  • operaţia de tipul 1: se dau două numere naturale x si y, între 1 şi N. Se cere să se reunească mulţimile în care se află elementul x, respectiv elementul y (se garantează că x şi y nu se vor afla în aceeaşi mulţime)
  • operaţia de tipul 2: se dau două numere naturale x şi y, între 1 şi N. Se cere să se afişeze DA dacă cele 2 elemente se află în aceeaşi mulţime, respectiv NU în caz contrar.

Date de intrare

Pe prima linie a fişierului de intrare disjoint.in se vor afla 2 numere, N şi M, reprezentând numărul de mulţimi, respectiv numărul de operaţii efectuate. Pe următoarele M linii se vor afla câte 3 numere, cod, x şi y, cod reprezentând tipul operaţiei, iar x şi y având semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire disjoint.out se vor afişa mai multe linii, fiecare linie conţinând DA sau NU, reprezentând răspunsul la interogarea corespunzătoare din fişierul de intrare.

Restricţii

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

Exemplu

disjoint.indisjoint.out
4 6
1 1 2
1 3 4
2 1 3
2 1 2
1 1 3
2 1 4
NU
DA
DA
Trebuie sa te autentifici pentru a trimite solutii. Click aici