Cod sursa(job #1889523)

Utilizator mihaitamoglanmihai moglan mihaitamoglan Data 22 februarie 2017 19:18:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.93 kb
type lista=^celula;
     celula=record
         info:longint;
         next:lista;
         end;
     tablou=array [1..100100]of lista;
     vector=array [1..100100]of 0..1;
var t,a:tablou;
    i,j,k,m,n,x,y:longint;
    f,g:text;
    viz:vector;
    aux:lista;


procedure adauga(x:longint;var aux:lista);
var r:lista;
begin
   new(r);
   r^.info:=x;
   r^.next:=aux;
   aux:=r;
end;

procedure dfs(x:longint);
var r:lista;
begin
 viz[x]:=1;
 r:=t[x];
 while r<>nil do
  begin
   if viz[r^.info]=0 then dfs(r^.info);
   r:=r^.next;
  end;
end;

begin
assign(f,'dfs.in');
assign(g,'dfs.out');
reset(f);
rewrite(g);
read(f,n,m);
for i:=1 to n do
 begin
  t[i]:=nil;
  viz[i]:=0;
 end;
for i:=1 to m do
   begin
    read(f,x,y);
    adauga(x,t[y]);
    adauga(y,t[x]);
   end;
k:=0;
for i:=1 to n do
 if viz[i]=0 then begin
    k:=k+1;
    dfs(i);
    end;
write(g,k);
close(f);
close(g);
end.