Cod sursa(job #3209175)

Utilizator prares06Papacioc Rares-Ioan prares06 Data 2 martie 2024 09:55:58
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include<bits/stdc++.h>

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

const int MAX = 1e5 + 5;
int Parent[MAX], Size[MAX];
int n, q, t, x, y;

void make_set(int v){
    Parent[v] = v;
    Size[v] = 1;
}

int GetParent(int v){
    if(Parent[v] == v)
        return v;
    return Parent[v] = GetParent(Parent[v]);
}

void make_union(int u, int v){
    u = GetParent(u);
    v = GetParent(v);
    if(u != v){
        if(Size[u] > Size[v])
            std::swap(u, v);
        Parent[u] = v;
        Size[v] += Size[u];
    }
}

int main(){
    fin >> n >> q;
    for(int i = 1; i <= n; ++i)
        make_set(i);
    while(q--){
        fin >> t >> x >> y;
        if(t == 1)
            make_union(x, y);
        else
            if(GetParent(x) == GetParent(y))
                fout << "DA\n";
            else
                fout << "NU\n";
    }
}