Cod sursa(job #3210294)

Utilizator iusty64Iustin Epanu iusty64 Data 5 martie 2024 21:14:50
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>

using namespace std;
const int Vmax = 100001;
int tata[Vmax];

int findRoot(int x){
    if(tata[x]<0){
        return x;
    }
    int root = findRoot(tata[x]);
    tata[x] = root;
    return root;
}

void uniune(int x, int y){
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    if(rootX == rootY){
        return;
    }
    if(tata[rootX] < tata[rootY]){
        swap(rootX, rootY);
    }
    tata[rootY] += tata[rootX];
    tata[rootX] = rootY;
}

int main(){
    int n, m;
    ifstream fin("disjoint.in");
    ofstream fout("disjoint.out");
    fin>>n>>m;
    for(int i=1;i<=n;i++){
        tata[i] = -1;
    }
    while(m--){
        int cerinta, x, y;
        fin>>cerinta>>x>>y;
        if(cerinta==1){
            uniune(x, y);
        }
        else{
            if(findRoot(x)==findRoot(y))
                fout<<"DA\n";
            else
                fout<<"NU\n";
        }
    }
}