Cod sursa(job #3370493)

Utilizator tomCipriTomescuCiprian tomCipri Data 26 octombrie 2026 14:28:20
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;


const int NMAX=1e5;
int p[NMAX+1], sz[NMAX+1];


int Find(int x) {
    while (x!=p[x]) {
        x=p[x];
    }
    return x;

}

void Union(int x,int y) {
    x=Find(x);
    y=Find(y);
    if (sz[x]>sz[y]) {
        p[y]=x;
        sz[x]+=sz[y];
    } else {
        p[x]=y;
        sz[y]==sz[x];
    }

}

int main() {

    ifstream fin("../disjoint.in");
    ofstream fout("../disjoint.out");
    int n,q;
    fin>>n>>q;
    for (int i=1;i<=n;i++) {
        p[i]=i;
        sz[i]=1;
    }
    for (int i=1;i<=n;i++) {
        int op,x,y;
        fin>>op>>x>>y;
        if (op==1) {
            Union(x,y);

        } else {
            fout<<(Find(x)==Find(y)? "Da\n": "Nu\n");
        }
    }


    return 0;
}