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

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema disjoint1:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3339 disjoint1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3339 disjoint1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3339 disjoint1