# PBinfo #3338 – disjoint – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se consideră N copii, numerotați de la 1 la N și fiecare face parte dintr-o clasă. Inițial sunt n clase și fiecare copil face parte din propria sa clasă. Se dau M operații de două tipuri:


1 x y – acțiune: clasele din care fac parte copiii cu numerele x și y se reunesc. Dacă x și y fac deja parte din aceeași clasă, operația nu se efectuează
2 x y – întrebare: copiii cu numerele x și y sunt sau nu în aceeași clasă?

Cerința
Răspundeți la toate întrebările de al doilea tip, în ordinea acestora.

Date de intrare
Programul citește de la tastatură numerele N și M, iar apoi M triplete de numere naturale de forma op x y, unde op poate lua doar valorile 1 și 2, aceste triplete reprezentând câte o operație.

Date de ieșire
Programul va afișa pe ecran, pe câte o linie, răspunsul la fiecare întrebare de tip 2. Dacă la întrebarea 2 x y răspunsul este afirmativ, adică x și y se află în aceeași clasă, atunci veți afișa DA, iar în caz contrar veți afișa NU.

Restricții și precizări

1 ≤ N ≤ 500
2 ≤ M ≤ 2000
va exista cel puțin o operație de tip 1 și cel puțin o operație de tip 2.

Exemplu:
Intrare

6 6
1 1 4
1 3 6
2 4 6
1 1 3
2 4 6
2 1 6
Ieșire

NU
DA
DA
Explicație
Sunt 6 copii și 6 operații. După primele două operații, elevii 1 și 4 sunt în aceeași clasă și 3 și 6 sunt în aceeași clasă. La întrebarea 2 4 6 răspunsul este evident NU. La a patra operație 1 și 3 sunt trecuți în aceeași clasă, deci va exista o clasă cu 4 copii: {1,3,4,6}, deci la ultimele două întrebări acum răspunsul este DA la ambele.

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int t[503], n, m;
int main()
{
    int i, j, x, y, p, q, op;
    cin >> n >> m;
    /// initializare
    for (i = 1; i <= n; i++)
        t[i] = i;
    for (i = 1; i <= m; i++)
    {
        cin >> op >> x >> y;
        if (op == 2)
        {
            if (t[x] == t[y]) cout << "DA\n";
            else cout << "NU\n";
        }
        else
        {
            if (t[x] != t[y])
            {
                p = t[x];
                q = t[y];
                for (j = 1; j <= n; j++)
                    if (t[j] == p) t[j] = q;
            }
        }
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3338)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3338/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3338/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)