Cod sursa(job #3212452)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 11 martie 2024 19:08:51
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <stdint.h>

const int32_t MAX_N = 100000;

int32_t prev[MAX_N];
int32_t height[MAX_N];

int32_t Root(int32_t node) {
    while(prev[node] != -1)
        node = prev[node];
    return node;
}
void Merge(int32_t rx, int32_t ry) {
    if(height[rx] > height[ry]) {
        prev[ry] = rx;
    } else if(height[rx] < height[ry]) {
        prev[rx] = ry;
    } else {
        prev[ry] = rx;
        ++height[rx];
    }
}

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

    int32_t n, m;
    fin >> n >> m;

    for(int32_t i = 0; i != n; ++i) {
        prev[i] = -1;
        height[i] = 1;
    }

    for(int32_t i = 0; i != m; ++i) {
        int32_t c, x, y;
        fin >> c >> x >> y;
        --x; --y;

        if(c == 1) {
            int32_t rx = Root(x), ry = Root(y);
            Merge(rx, ry);
        } else {
            if(Root(x) == Root(y)) {
                fout << "DA\n";
            } else {
                fout << "NU\n";
            }
        }
    }

    fin.close();
    fout.close();

    return 0;
}