Cod sursa(job #3301103)

Utilizator DasapSapunaru Daniel Dasap Data 21 iunie 2025 18:22:50
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include<fstream>
using namespace std;ifstream fin("disjoint.in");ofstream fout("disjoint.out");
int n,m,i,op,x,y,tata[100001],h[100001];
int radacina(int n){
int root=n;while(tata[root]!=root)root=tata[root];
while(n!=tata[n]){
    int aux=tata[n];
    tata[n]=root;
    n=aux;
}return root;
}
void unite(int x,int y){
int rootx=radacina(x),rooty=radacina(y);
if(h[rootx]<h[rooty])tata[rootx]=rooty;
else if(h[rooty]<h[rootx])tata[rooty]=rootx;
else{tata[rootx]=rooty;h[rooty]++;}
}
int main()
{
    fin>>n>>m;for(i=1;i<=n;i++){tata[i]=i,h[i]=1;}for(i=1;i<=m;i++){
    fin>>op>>x>>y;if(op==1)unite(x,y);
    else if(radacina(x)==radacina(y))fout<<"YES\n";else fout<<"NU\n";}
    return 0;
}