Cod sursa(job #1012198)
Utilizator | Livia Magureanu livlivi | Data | 18 octombrie 2013 14:43:17 |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include<cstdio>
using namespace std;
int t[100001];
int rad(int x){
if (t[x]==0) return x;
t[x]=rad(t[x]);
return t[x];
}
void reu(int x,int y){
if (t[x]==0) t[x]=y;
else reu(t[x],y);
t[x]=y;
}
int main(){
freopen ("disjoint.in","r",stdin);
freopen ("disjoint.out","w",stdout);
int n,m,i,c,x,y;
scanf ("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf ("%d%d%d",&c,&x,&y);
if (c==1) reu(x,y);
else {
if (rad(x)==rad(y)) printf ("DA\n");
else printf ("NU\n");
}
}
return 0;
}