Cod sursa(job #3211039)

Utilizator Toni07Stoica Victor Toni07 Data 8 martie 2024 09:14:48
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 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 unite(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 f ("disjoint.in");
    ofstream g ("disjoint.out");
    f >> n >> m;
    for(int i=1;i<=n;i++){
        tata[i] = -1;
    }
    while(m--){
        int q, x, y;
        f >> q >> x >> y;
        if(q==1){
            unite(x, y);
        }
        else{
            if(findRoot(x)==findRoot(y))
                g << "DA\n";
            else
                g << "NU\n";
        }
    }
}