Cod sursa(job #3208697)

Utilizator devilexeHosu George-Bogdan devilexe Data 29 februarie 2024 12:29:22
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
// TODO: disjointed, apm
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5;
int N, M;
int dad[MAXN + 5], depth[MAXN + 5];

int dag_getRoot(int x) {
    if(dad[x] == x)
        return x;
    return (dad[x] = dag_getRoot(dad[x]));
}
void dag_union(int x, int y) {
    int rootX = dag_getRoot(x), rootY = dag_getRoot(y);
    if (rootX == rootY)
        return;
    if(depth[rootX] <= depth[rootY]) {
        dad[rootX] = rootY;
        if(depth[rootX] == depth[rootY])
            ++depth[rootY];
    } else {
        dad[rootY] = rootX;
    }
}
bool query(int x, int y) {
    int rootX = dag_getRoot(x), rootY = dag_getRoot(y);
    return (rootX == rootY);
}

int main()
{
    fin >> N >> M;
    // init dad
    for (int i = 1; i <= N; ++i)
        dad[i] = i;

    int t, a, b;
    while(M--) {
        fin >> t >> a >> b;
        if(t == 1)
            dag_union(a, b);
        else
            fout << (query(a, b) ? "DA\n" : "NU\n");
    }
    return 0;
}