Cod sursa(job #152347)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 9 martie 2008 13:14:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.21 kb
type adresa=^nod;
     nod= record inf:longint; adr:adresa; end;

var n,m,i,k:longint;
    p:array[1..100000] of adresa;
    uz:array[1..100000] of byte;

procedure citire;
        var f:text;
            i,x,y:longint;
            q:adresa;
        begin
        assign(f,'dfs.in');
        reset(f);
        readln(f,n,M);
        for i:=1 to n do p[i]:=nil;
        for i:=1 to m do begin
            readln(f,x,y);
            new(q);
             q^.inf:=x;
             q^.adr:=p[y];
             p[y]:=q;
            new(q);
             q^.inf:=y;
             q^.adr:=p[x];
             p[x]:=q;
            end;
        close(f);
        end;

procedure scrie(k:longint);
        var f:text;
        begin
        assign(f,'dfs.out');
         rewrite(f);
         writeln(f,k);
         close(f);
        end;

procedure df(k:longint);
        var q:adresa;
        begin
        uz[k]:=1;
        q:=p[k];
        while q<>nil do begin
              if uz[q^.inf]=0 then
                 df(q^.inf);
              q:=q^.adr;
              end;
        end;

begin
citire;
for i:=1 to n do
    if uz[i]=0 then begin
       inc(k);
       df(i);
    end;
scrie(k);
end.