Cod sursa(job #399149)

Utilizator nickyyLal Daniel Emanuel nickyy Data 19 februarie 2010 21:40:01
Problema Parcurgere DFS - componente conexe Scor 65
Compilator fpc Status done
Runda Arhiva educationala Marime 1.2 kb
const infile='dfs.in';
  outfile='dfs.out';
  maxn=100001;
  maxm=200001;
type muchie=record
        e1,e2:longint;
        end;
var n,nr,m:longint;
  a:array[1..maxm]of muchie;
  tata,niv:array[0..maxn]of longint;

 procedure citire;
 var f:text;
   i,j,k:longint;
 begin
   assign(f,infile); reset(f); readln(f,n,m);
   for k:=1 to m do readln(f,a[k].e1,a[k].e2);
   close(f);
 end;

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

 procedure union(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;

 procedure solve;
 var i,j:integer;
 begin
   fillchar(tata,sizeof(tata),0); niv:=tata;
   while(m>0)do begin
     i:=find(a[m].e1); j:=find(a[m].e2);
     if(i<>j)then union(i,j);
     dec(m);
     end;
 end;

 procedure afisare;
 var f:text;
   i:integer;
 begin
  assign(f,outfile); rewrite(f); nr:=0;
  for i:=1 to n do if(tata[i]=0)then inc(nr);
  write(f,nr);
  close(f);
 end;

begin
 citire; solve; afisare;
end.