Cod sursa(job #1351764)

Utilizator mariusadamMarius Adam mariusadam Data 21 februarie 2015 11:31:31
Problema Parcurgere DFS - componente conexe Scor 45
Compilator fpc Status done
Runda Arhiva educationala Marime 0.88 kb
program componente_conexe;
type lista=array[0..1,1..200000] of longint;
     pornire=array[1..100000] of longint;
     vizitat=array[1..100000] of 0..1;
var l:lista;
    p:pornire;
    viz:vizitat;
    n,m,nr_comp,i:longint;
    f,g:text;

procedure citire;
var i,j,k,z:integer;
begin
 readln(f,n,m);
 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.