# PBinfo #3339 – disjoint1 – Rezolvare C++

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

## Enunț

Se consideră un graf cu N noduri numerotate de la 1 la N și M operații de trei tipuri:


1 x y – se adaugă în graf muchia (x, y). Dacă muchia există deja, operația nu se efectuează
2 x y – întrebare: nodurile x și y se află sau nu în aceeași componentă conexă?
3 – întrebare: care este numărul maxim de noduri dintr-o componentă conexă?

Cerința
Trebuie să răspundeți la toate întrebările de tip 2 și 3.

Date de intrare
Programul citește de la tastatură numerele N și M, iar pe următoarele M linii se află operațiile date fie prin trei valori de forma op x y (pentru operațiile de tip 1 și 2), fie printr-o singură valoare 3 (pentru operațiile de tip 3). 

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

Restricții și precizări

3 ≤ N ≤ 32.000
3 ≤ M ≤ 300.000
va exista cel puțin o operație de fiecare tip.

Exemplu:
Intrare

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

NU
DA
4
Explicație
Sunt 6 noduri și 6 operații. După primele două operații, nodurile 1 și 4 sunt în aceeași componentă conexă și 3 și 6 sunt în aceeași componentă conexă. La întrebarea 2 4 6 răspunsul este evident NU. La a patra operație 1 și 3 sunt trecute în aceeași componentă conexă, deci va exista o componentă conexă cu 4 noduri: {1,3,4,6}, deci la întrebarea 2 4 6 răspunsul este DA, iar la ultima operație de tip 3 răspunsul este 4 (componenta conexă maximală are patru noduri).

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int t[33003], n;
int c[33003], M;
void Union(int x, int y)
{
    c[x] += c[y];
    M = max(M, c[x]);
    t[y] = x;
}
int Find(int x)
{
    int rad, y;
    rad = x;
    while (t[rad] != 0)
        rad = t[rad];
    /// comprimare drum
    while (x != rad)
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }
    return rad;
}
int main()
{
    int m, i, x, y, op;
    cin >> n >> m;
    /// initializare
    for (i = 1; i <= n; i++)
        c[i] = 1;
    while (m--)
    {
        cin >> op;
        if (op == 3) cout << M << "\n";
        else /// 1 sau 2
        {
            cin >> x >> y;
            x = Find(x);
            y = Find(y);
            if (op == 1)
            {
                if (x != y) Union(x, y);
            }
            else /// op == 2
            {
                if (x == y) cout << "DA\n";
                else cout << "NU\n";
            }
        }
    }
    return 0;
}
```

## Resurse

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