Cod sursa(job #1380032)

Utilizator George97George Linut George97 Data 6 martie 2015 21:15:08
Problema Parcurgere DFS - componente conexe Scor 15
Compilator fpc Status done
Runda Arhiva educationala Marime 0.9 kb
type ref=^adresa;
     adresa=record
     nr:longint;
     urm:ref;
     end;
var a:array[1..200001] of ref;
    i,j,k,l,n,m:longint;
    viz:array[1..100001] of longint;
    pp:ref;
    f,g:text;

procedure dfs(x:longint);
var i:longint;
    p:ref;
begin
viz[x]:=k;
p:=a[x];
while p<>nil do
  begin
  if viz[p^.nr]=-1 then dfs(p^.nr);
  p:=p^.urm;
  end;
end;

begin
assign(f,'dfs.in');
reset(f);
assign(g,'dfs.out');
rewrite(g);
read(f,n,m);
for i:=1 to n do
  a[i]:=nil;
for i:=1 to m do
  begin
  read(f,k,l);
  if a[k]=nil then
    begin
    new(a[k]);
    a[k]^.nr:=l;
    a[k]^.urm:=nil;
    end
              else
    begin
    new(pp);
    pp^.nr:=l;
    pp^.urm:=a[k];
    a[k]:=pp;
    end;
  end;
k:=0;
for i:=1 to n do
   viz[i]:=-1;
for i:=1 to n do
  if viz[i]=-1 then
    begin
    inc(k);
    dfs(i);
    end;
writeln(g,k);
close(g);
end.