Pagini recente » Cod sursa (job #1785015) | Cod sursa (job #17226) | Cod sursa (job #889660) | Cod sursa (job #1828248) | Cod sursa (job #172104)
Cod sursa(job #172104)
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
dfs(p^.crt); {daca nu am vizitat nodul p^.crt, parcurg toti fiii sai}
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 totii 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.