Cod sursa(job #2681337)

Utilizator MogageMogage Nicolae Mogage Data 5 decembrie 2020 11:48:53
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>

int T[5005], Rang[5005];

int Radacina(int k) {
    if (T[k] == 0)
        return k;
    else
    {
        int x = Radacina(T[k]);
        T[k] = x;
        return x;
    }
}

void Unire(int k, int p)
{
    int rk = Radacina(k), rp = Radacina(p);
    if (rk != rp)
    {
        if (Rang[rk] > Rang[rp])
            T[rp] = rk;
        else
        {
            T[rk] = rp;
            if (Rang[rk] == Rang[rp])
                Rang[rp] ++;
        }
    }
}

int main()
{
    int n, m, op, x, y;
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        std::cin >> op >> x >> y;
        if (op == 1)
            Unire(x, y);
        else {
            int r_x = Radacina(x), r_y = Radacina(y);
            if (r_x == r_y)
                std::cout << "DA\n";
            else std::cout << "NU\n";
        }
    }
	return 0;
}