Cod sursa(job #3208738)

Utilizator daliaptvPetrovici Dalia daliaptv Data 29 februarie 2024 17:44:01
Problema Paduri de multimi disjuncte Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int rep[10001],n,m,k,x,y;
int reprezentant(int p){
    if(rep[p]==p){
        return p;
    }
    rep[p]=reprezentant(rep[p]);
    return rep[p];
}

void unire(int a, int b){
    int rep_a=reprezentant(a);
    int rep_b=reprezentant(b);
    if(rep_a!= rep_b){
        rep[rep_a]=rep_b;
    }

}
int main()
{
    fin>>n>>m;
    for(int i=0; i<n; i++) rep[i]=i;

    for(int i=0; i<m; i++){
        fin>>k>>x>>y;

    if(k==1){
        unire(x,y);
    }
    else{
        int a1=reprezentant(x);
        int b1=reprezentant(y);
        if(a1==b1) fout<<"DA"<<'\n';
        else fout<<"NU"<<'\n';
    }
    }
}