Cod sursa(job #3373328)

Utilizator TLuca2021Teodorescu Luca Nicolae TLuca2021 Data 6 noiembrie 2026 16:42:05
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int identify(int node, vector<int> &father){
    if(father[node] == node){
        return node;
    }
    return father[node] = identify(father[node], father);
}
void unify(int first_node, int second_node, vector<int> &father, vector<int> &height){
    int first_father = identify(first_node, father);
    int second_father = identify(second_node, father);
    if(height[first_father] >= height[second_father]){
        father[second_father] = first_father;
        height[first_father] = max(height[first_father], height[second_father] + 1);
    }
    else{
        father[first_father] = second_father;
    }
}
int main(){
    int n, m;
    fin >> n >> m;
    vector<int> father(n), height(n);
    for(int i = 0; i < n; i++){
        father[i] = i;
        height[i] = 0;
    }
    for(int i = 0; i < m; i++){
        int code, first_node, second_node;
        first_node--;
        second_node--;
        fin >> code >> first_node >> second_node;
        if(code == 1){
            unify(first_node, second_node, father, height);
        }
        else if(code == 2){
            int first_father = identify(first_node, father);
            int second_father = identify(second_node, father);
            if(first_father == second_father){
                fout << "DA" << '\n';
            }
            else{
                fout << "NU" << '\n';
            }
        }
    }
    return 0;
}