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

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.

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 disjoint:

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

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 #3338 disjoint

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3338 disjoint 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 #3338 disjoint