Cod sursa(job #172105)

Utilizator StigmaSimina Pitur Stigma Data 5 aprilie 2008 19:15:26
Problema Sortare topologica Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.58 kb
program sortare_topologica;
type point=^nod;
     nod=record
      crt:longint;
      uf:point;
     end;
var n,m,i,x,y:longint;
fii:array[1..50000] of point; {retin in fii[T] toti fiii nodului T}
viz:array[1..50000] of byte; {retin daca am vizitat nodul, prin 0 si 1}
f1,f2:text;
l:point; {lista in care retin nodurile sortate}



procedure introduce_date(tata,fiu:longint);
var p:point;
begin
 new(p);
 p^.crt:=fiu;
 p^.uf:=fii[tata];
 fii[tata]:=p;   {am introdus nodul fiu lista fiilor nodului 'tata'}
end;



procedure dfs(d:longint);
var p:point;
begin
 viz[d]:=1;    {marchez nodul d ca fiind vizitat}
 p:=fii[d];    {parcurg lista fii[d] care contine toti fiii nodului d}

 while p<>nil do          {cat timp lista nu e vida}
  begin
   if viz[p^.crt]=0 then    {daca nu am vizitat nodul p^.crt si, deci, nu l-am introdus in lista L}
     dfs(p^.crt);
   p:=p^.uf;           {trec la urmatorul fiu al nodului d}
  end;

{am iesit din while deoarece p=nil, deci nodul d nu mai are fii}
{inseamna ca toti fiii nodului d, daca au existat, au fost deja introdusi in lista L}
{introducem nodul d inaintea fiilor sai, in lista L}

 new(p);
 p^.crt:=d;
 p^.uf:=l;
 l:=p;
end;



begin
assign(f1,'sortaret.in');reset(f1);
assign(f2,'sortaret.out');rewrite(f2);
readln(f1,n,m);
for i:=1 to m do
begin
readln(f1,x,y);
introduce_date(x,y);
end;

for i:=1 to n do
if viz[i]=0 then    {daca nodul i nu a fost introdus in lista L}
  dfs(i);

while l<>nil do     {afisam lista solutie L}
begin
write(f2,l^.crt,' ');
l:=l^.uf;
end;

close(f1);
close(f2);
end.