Cod sursa(job #157155)

Utilizator Clau2000GOREA CLAUDIU-CRISTIAN Clau2000 Data 12 martie 2008 21:31:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.13 kb
type legatura=^nod;
     nod=record
         inf:longint;
         urm:legatura;
     end;
{--------------------------------------}
var lista:array[1..100000] of legatura;
    f,g:text;
    p:legatura;
    n,m,nr,i,x,y:longint;
    viz:array[1..100000] of 0..1;
{--------------------------------------}
procedure df(x:longint);
var p:legatura;
begin
     viz[x]:=1;
     p:=lista[x];
     while p<>nil do
     begin
          if viz[p^.inf]=0 then
             df(p^.inf);
          p:=p^.urm;
     end;
end;
{--------------------------------------}
begin
   assign(f,'dfs.in');
   assign(g,'dfs.out');
   reset(f);
   rewrite(g);
   readln(f,n,m);
   for i:=1 to n do
      lista[i]:=nil;
   for i:=1 to m do
   begin
      readln(f,x,y);
      new(p);
      p^.inf:=x;
      p^.urm:=lista[y];
      lista[y]:=p;
      new(p);
      p^.inf:=y;
      p^.urm:=lista[x];
      lista[x]:=p;
   end;
   for i:=1 to n do
      viz[i]:=0;
   nr:=0;
   for i:=1 to n do
      if viz[i]=0 then
      begin
         df(i);
         inc(nr);
      end;

   writeln(g,nr);
   close(f);
   close(g);
end.