Cod sursa(job #1124737)

Utilizator EuBossuletMuntea Andrei EuBossulet Data 26 februarie 2014 13:34:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.17 kb
Program dfs;
type lista=^list;
     list=record
        info:longint;
        leg:lista;
     end;
var v:array[1..100000] of lista;
    poz:array[1..100000] of 0..1;
    f,q:text;
    n,m,i,j,x,y,nr:longint;
procedure push(var p:lista; x:longint);
var q,h:lista;
begin
        if p=nil then begin
                new(q);
                q^.leg:=nil;
                q^.info:=x;
                p:=q;
        end
        else begin
                h:=p;
                while h^.leg<>nil do h:=h^.leg;
                new(q);
                q^.info:=x;
                q^.leg:=nil;
                h^.leg:=q;
        end;
end;
procedure back(p:lista);
var q:lista;
begin
      q:=p;
      while q<>nil do
      begin
        if poz[q^.info]=0 then begin poz[q^.info]:=1; back(v[q^.info]); end;
        q:=q^.leg;
      end
end;

begin
assign(f,'dfs.in');
reset(f);
assign(q,'dfs.out');
rewrite(q);
readln(f,n,m);
for i:=1 to m do begin read(f,x,y); push(v[x],y); push(v[y],x); end;
for i:=1 to n do
        if poz[i]=0 then begin
        inc(nr);
        poz[i]:=1;
        back(v[i]);
        end;
writeln(q,nr);
close(f);
close(q);
end.