Cod sursa(job #1891270)

Utilizator DimaTCDima Trubca DimaTC Data 23 februarie 2017 21:08:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.45 kb
type   lista= ^celula;
       celula=record
               info: longint;
               next: lista;
              end;

var n,u,m,rs,x,y,i: longint;
    lda: array[1..100100] of lista;
    viz: array[1..100100] of 0..1;
    fi, fo: text;

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

procedure dfs(x: longint);
var r: lista;
          begin
             viz[x]:=1;
             r:=lda[x];
             while r<>nil do begin
                                 if viz[r^.info]=0 then dfs(r^.info);
                                 r:=r^.next;
                             end;
            end;

begin
      assign(fi,'dfs.in');
      assign(fo,'dfs.out');
      reset(fi);
      rewrite(fo);
      read(fi,n,m);
      for i:=1 to n do begin
                          lda[i]:=nil;
                          viz[i]:=0;
                       end;

      for i:=1 to m do begin
                         read(fi,x,y);
                         add(x,lda[y]);
                         add(y,lda[x]);
                       end;
      close(fi);
      rs:=0;
      for i:=1 to n do
               if viz[i]=0 then begin
                                   rs:=rs+1;
                                   dfs(i);
                                end;
      writeln(fo,rs);
      close(fo);

end.