Cod sursa(job #209871)

Utilizator RobybrasovRobert Hangu Robybrasov Data 25 septembrie 2008 09:57:12
Problema Parcurgere DFS - componente conexe Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 0.79 kb
type    adr=^noduri;
        noduri=record val:longint; urm:adr; end;
var     L:array[1..100000] of adr;
        E:array[1..100000] of boolean;
        n,m,i,j,k:longint;
        p:adr;
        f:text;

procedure df(nod:longint);
var p:adr;
begin
  E[nod]:=true;
  p:=L[nod];
  while p<>nil do
    begin
      if not E[p^.val] then df(p^.val);
      p:=p^.urm;
    end;
end;

begin
  assign(f,'dfs.in');
  reset(f);
  readln(f,n,m);
  for i:=1 to m do
    begin
      readln(f,i,j);
      new(p);
      p^.val:=j; p^.urm:=L[i];
      L[i]:=p;
      new(p);
      p^.val:=i; p^.urm:=L[j];
      L[j]:=p;
    end;
  close(f);
  k:=0;
  for i:=1 to n do
    if not E[i] then begin inc(k); df(i); end;
  assign(f,'dfs.out');
  rewrite(f);
  write(f,k);
  close(f);
end.