Cod sursa(job #1756804)

Utilizator preda.andreiPreda Andrei preda.andrei Data 13 septembrie 2016 17:46:06
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>

using namespace std;

#define NMAX 100001

struct Nod
{
    int tata;
    int rang = 1;
};

Nod noduri[NMAX];

bool inAcelasiArbore(int x, int y);
void reuneste(int x, int y);
int radacina(int x);

int main()
{
    ifstream fin("disjoint.in");
    ofstream fout("disjoint.out");

    int n, m;
    fin >> n >> m;

    while (m--) {
        int r, x, y;
        fin >> r >> x >> y;

        if (r == 1) {
            reuneste(x, y);
        }
        else {
            fout << ((inAcelasiArbore(x, y)) ? "DA" : "NU") << "\n";
        }
    }

    return 0;
}

bool inAcelasiArbore(int x, int y)
{
    int rx = radacina(x);
    int ry = radacina(y);

    while (x != rx) {
        int cx = x;
        x = noduri[x].tata;
        noduri[cx].tata = rx;
    }

    return rx == ry;
}

void reuneste(int x, int y)
{
    int rx = radacina(x);
    int ry = radacina(y);

    if (noduri[rx].rang > noduri[ry].rang) {
        swap(rx, ry);
    }

    noduri[ry].tata = rx;
    noduri[rx].rang += noduri[ry].rang;
}

int radacina(int x)
{
    while (noduri[x].tata != 0) {
        x = noduri[x].tata;
    }
    return x;
}