Cod sursa(job #166208)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 27 martie 2008 17:50:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.39 kb
program dfs;
type pnod = ^nod;
      nod = record
            info : longint;
            next : pnod;
            end;
var A,Ultim : array [1..100000] of pnod;
    urm : pnod;
    ok : array [1..100000] of boolean;
    i,j,n,m,x,y,nr : longint;
    f,g : text;

procedure df(x:longint);
begin

ok[x] := false;

while (A[x]<>nil) do begin
if ok[A[x]^.info] then df(A[x]^.info);
A[x] := A[x]^.next;
end;


end;

begin
assign(f,'dfs.in');
reset(f);
assign(g,'dfs.out');
rewrite(g);

readln(f,n,m);

for i := 1 to n do begin
ok[i] := true;
A[i] := nil;
end;

for i := 1 to m do begin
readln(f,x,y);
if A[x]=nil then begin
              new(A[x]);
              A[x]^.info := y;
              A[x]^.next := nil;
              Ultim[x] := A[x];
              end
else begin
     new(urm);
     urm^.info := y;
     urm^.next := nil;
     Ultim[x]^.next := urm;
     Ultim[x] := urm;
     end;

if A[y]=nil then begin
              new(A[y]);
              A[y]^.info := x;
              A[y]^.next := nil;
              Ultim[y] := A[y];
              end
else begin
     new(urm);
     urm^.info := x;
     urm^.next := nil;
     Ultim[y]^.next := urm;
     Ultim[y] := urm;
     end;
end;

nr := 0;


for i := 1 to n do
if ok[i] then begin
              nr := nr+1;
              df(i);
              end;

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