Cod sursa(job #702159)

Utilizator amaliutzzaGoia Amalia amaliutzza Data 1 martie 2012 20:00:47
Problema Parcurgere DFS - componente conexe Scor 5
Compilator fpc Status done
Runda Arhiva educationala Marime 1.04 kb
program compconexe;

type pnod=^nod;
     nod=record inf:longint; urm:pnod; end;

var fi,fo:text;
    l:array[1..100000] of pnod;
    i,n,m,nrc:integer;
    viz:array[1..100000] of 0..1;

    procedure citire;
    var i,x,y:integer;
        p:pnod;
    begin
        readln(fi,n,m);

        for i:=1 to m do l[i]:=nil;

        for i:=1 to m do
          begin
              readln(fi,x,y);
              new(p);
              p^.inf:=y;
              p^.urm:=l[x];
              l[x]:=p;
          end;
    end;

    procedure df(nod:integer);
    var p:pnod;
    begin
        viz[nod]:=1;
        p:=l[nod];
        while p<>nil do
          begin
              df(p^.inf);
              p:=p^.urm;
          end;
    end;



begin

    assign(fi,'dfs.in'); reset(fi);
    assign(fo,'dfs.out'); rewrite(fo);

      citire;

      for i:=1 to n do
        if viz[i]=0 then
          begin
              inc(nrc);
              df(i);
          end;

      writeln(fo,nrc);

    close(fi); close(fo);
end.