Cod sursa(job #1340427)

Utilizator mihai1996Toader Mihai mihai1996 Data 11 februarie 2015 20:02:04
Problema Parcurgere DFS - componente conexe Scor 60
Compilator fpc Status done
Runda Arhiva educationala Marime 0.93 kb
program dfs;
type ref=^inr;
     inr=record
       nd:integer;
       adr_urm:ref;
     end;
     lista_a=array[1..100000] of ref;
var f,g:text;
    i,x,y,n,m,nr:integer;
    p:ref;
    viz:array[1..100000] of integer;
    l:lista_a;

procedure df(nod,nr:integer);
var p:ref;
begin
  viz[nod]:=1;
  p:=l[nod];
  while p<>nil do
   begin
    if viz[p^.nd]=0 then
      df(p^.nd,nr);
    p:=p^.adr_urm;
   end;

end;

begin
  assign(f,'dfs.in'); reset(f);
  assign(g,'dfs.out'); rewrite(g);
  readln(f,n,m);
  for i:=1 to n do
    l[i]:=nil;
  for i:=1 to m do
    begin
      readln(f,x,y);
      new(p);
      p^.adr_urm:=L[x];
      p^.nd:=y;
      l[x]:=p;
      new(p);
      p^.adr_urm:=l[y];
      p^.nd:=x;
      l[y]:=p;
    end;
  nr:=0;
  for i:=1 to n do
      if viz[i]=0 then
        begin
          inc(nr);
          df(i,nr);
        end;
  writeln(g,nr);
  close(F);
  close(g);
end.