Cod sursa(job #401496)

Utilizator nickyyLal Daniel Emanuel nickyy Data 22 februarie 2010 21:28:43
Problema Paduri de multimi disjuncte Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 0.85 kb
const infile='disjoint.in';
  outfile='disjoint.out';
  maxnm=100001;
var tata,niv:array[0..maxnm]of longint;
  n,m,x,y:longint;
  fi,fo:text;
  op:1..2;

 procedure unire(x,y:longint);
 begin
   if(niv[x]>niv[y])then tata[y]:=x
   else begin
     tata[x]:=y;
     if(niv[x]=niv[y])then inc(niv[y]);
     end;
 end;

 function gaseste(i:longint):longint;
 var r,y,t:longint;
 begin
   r:=i;
   while(tata[r]<>0)do r:=tata[r];
   y:=i;
   while(y<>r)do begin t:=tata[y]; tata[y]:=r; y:=t; end;
   gaseste:=r;
 end;

begin
 assign(fi,infile); reset(fi);
 assign(fo,outfile); rewrite(fo);
 readln(fi,n,m);
 while(m>0)do begin
   readln(fi,op,x,y); dec(m);
   if(op=1)then unire(x,y)
   else begin
    x:=gaseste(x); y:=gaseste(y);
    if(x=y)then writeln(fo,'DA')
    else writeln(fo,'Nu');
    end;
   end;
 close(fi); close(fo);
end.