Cod sursa(job #1017340)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 27 octombrie 2013 18:06:09
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#define maxnm 100005
using namespace std;

ifstream fi("disjoint.in");
ofstream fo("disjoint.out");

int tata[maxnm],rang[maxnm];
int i,n,m;

int radacina(int x){
    int aux,k=x;

    while (x!=tata[x]) x=tata[x];
    while (k!=tata[k]) {aux=k; k=tata[k]; tata[k]=x;}
    
    return x;
}

void uneste(int x,int y){
     if (rang[x]>rang[y]) tata[y]=x;
                     else tata[x]=y;
     if (rang[x]==rang[y]) rang[y]++;
}

int main(void){
    int oper1,x,y;
    fi>>n>>m;
    
    for(i=1;i<=n;i++) {
                       tata[i]=i;
                       rang[i]=0;
                      }
    
    for(i=1;i<=m;i++) {
                       fi>>oper1>>x>>y;
                       if (oper1==1) uneste(radacina(x),radacina(y));
                       else {
                             if (radacina(x)==radacina(y)) fo<<"DA\n";
                             else fo<<"NU\n";
                            } 
                      }
    
    fi.close();
    fo.close();
    return 0;
}