Cod sursa(job #1106112)

Utilizator azkabancont-vechi azkaban Data 12 februarie 2014 15:33:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.24 kb
Program dfs;
type lista=^celula;
       celula=record
         info:longint;
         pred:lista;
       end;

var lda:array[1..100000] of lista;
    viz:array[1..100000] of byte;
    a,b,n,m,k,i:longint;

procedure add(v:longint; var p:lista);
   var r:lista;
    begin
         new(r);
         r^.info:=v;
         r^.pred:=p;
         p:=r;
    end;

procedure dfs(nod:longint);
    var r:lista;
    begin
           viz[nod]:=1;
           r:=lda[nod];
           while r<>nil do begin
                                 if viz[r^.info]=0 then dfs(r^.info);
                                 r:=r^.pred;
                           end;
    end;
begin
    assign(input,'dfs.in'); reset(input);
    assign(output,'dfs.out'); rewrite(output);
    readln(n,m);
    for i:=1 to n do lda[i]:=nil;
    for i:=1 to m do begin
                          readln(a,b);
                          add(a,lda[b]);
                          add(b,lda[a]);
                     end;
   for i:=1 to n do
                   if viz[i]=0 then begin
                                          inc(k);
                                          dfs(i);
                                    end;
   writeln(k);
   close(input);
   close(output);
end.