Cod sursa(job #1351738)

Utilizator mariusadamMarius Adam mariusadam Data 21 februarie 2015 11:29:02
Problema Parcurgere DFS - componente conexe Scor 45
Compilator fpc Status done
Runda Arhiva educationala Marime 1.04 kb
program componente_conexe;
type lista=array of array of longint;
     pornire=array of longint;
     vizitat=array of 0..1;
     //buff=array of byte;
var l:lista;
    p:pornire;
    viz:vizitat;
    //bi,bo:buff;
    n,m,nr_comp,i:longint;
    f,g:text;

procedure citire;
var i,j,k,z:integer;
begin
 readln(f,n,m);
 setlength(l,2,2*m+1);
 setlength(p,n+1);
 setlength(viz,n+1);
 //setlength(bi,m+1); settextbuf(f,bi);
 //setlength(bo,m+1); settextbuf(g,bo);
 z:=0;
 for k:=1 to m do
  begin
   readln(f,i,j);
   z:=z+1;
   l[0,z]:=j; l[1,z]:=p[i]; p[i]:=z;
   z:=z+1;
   l[0,z]:=i; l[1,z]:=p[j]; p[j]:=z;
  end;
end;

procedure df(nod:longint);
var z:longint;
begin
 viz[nod]:=1; z:=p[nod];
 while z<>0 do
  begin
   if viz[l[0,z]]=0 then
    df(l[0,z]);
   z:=l[1,z];
  end;
end;

begin
 assign(f,'dfs.in'); reset(f);
 assign(g,'dfs.out'); rewrite(g);
 nr_comp:=0;
 citire;
 for i:=1 to n do
  if viz[i]=0 then
   begin
    df(i); nr_comp:=nr_comp+1;
   end;
 write(g,nr_comp);
 close(f);
 close(g);
end.