Cod sursa(job #2549531)

Utilizator goblinupufosPopescu Traian goblinupufos Data 17 februarie 2020 19:22:06
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int tatic[1000000];
int cati[1000000];

int Find( int x ) {

    int y, z;
    y = x;

    while(tatic[x] != x) {

        x = tatic[x];

    }

    while(tatic[y] != y) {

        z = tatic[y];
        tatic[y] = x;
        y = z;

    }

    return x;

}

void Union( int x, int y ) {

    if ( cati[x] > cati[y] ) {

        cati[x] += cati[y];
        cati[y] = 0;
        tatic[y] = x;

    } else {

        cati[y] += cati[x];
        cati[x] = 0;
        tatic[x] = y;

    }

}

int main() {

    int n;
    fin>>n;

    for ( int i = 1; i <= n; ++i ) {

        tatic[i] = i;
        cati[i] = 1;

    }

    for ( int i = 1; i <= n; ++i ) {

        int op;
        cin>>op;

        if ( op == 1 ) {

            int x, y;
            fin >> x >> y;
            Union(Find(x), Find(y));

        } else {

            int x, y;
            fin >> x >> y;

            if ( Find(x) == Find(y) ) {

                fout << "DA" << "\n";

            } else {

                fout << "NU" << "\n";

            }

        }

    }

    return 0;

}