Cod sursa(job #282004)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 16 martie 2009 18:49:00
Problema Sortare topologica Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.98 kb
Program Sortare_Topologica;

type point=^nod;
     nod=record
        urm:point;
        val:longint;
     end;


var a:Array[1..50000] of point;
    grad,v:array[1..50000] of longint;
    f,g:text;
    n,m,i,nr,x,y:longint;
    p:point;

begin
 assign(f,'sortaret.in'); reset(f);
 assign(g,'sortaret.out'); rewrite(g);
 read(f,n,m);
 for i:=1 to m do begin
        read(f,x,y);
        inc(grad[x]);
        new(p);
        p^.val:=x; p^.urm:=a[y]; a[y]:=p;
 end;
 nr:=0;
 for i:=1 to n do
        if grad[i]=0 then begin
                nr:=nr+1;
                v[nr]:=i;
        end;
 for i:=1 to n do begin
        p:=a[v[i]];
        while p<>NIL do begin
                dec(grad[p^.val]);
                if grad[p^.val]=0 then begin
                        nr:=nr+1;
                        v[nr]:=p^.val;
                end;
                p:=p^.urm;
        end;
 end;
 for i:=n downto 1 do
        write(g,v[i],' ');
 close(f); close(g);
end.