Cod sursa(job #552470)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 12 martie 2011 13:38:50
Problema Sortare topologica Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.13 kb
type muchie = ^nod;
     nod = record n:longint; a:muchie; end;

var v:array [1..2, 1..50000] of muchie;
    chk:array [1..50000] of boolean;
    p, r, ed:muchie;
    i, m, n, x, y:longint;
    f, g:text;

procedure dfs (a:muchie; c:longint);
var ii:integer;
    q:muchie;
  begin
  q:=a;
  for ii := 1 to a^.n do
    begin
    q:=q^.a;
    if chk[q^.n] = false then
      begin
      chk[q^.n] := true;
      dfs (v[1, q^.n], q^.n);
      end;
    end;
  new (p); p^.n:=c; p^.a:=ed; ed:=p;
  end;

begin
assign (f, 'sortaret.in'); reset (f);
assign (g, 'sortaret.out'); rewrite (g);
read (f, n, m);
for i := 1 to n do begin new (v[1, i]); v[1, i]^.n:= 0; end;

for i := 1 to m do
  begin
  read (f, x, y);
  if v[1, x]^.n > 0 then r:= v[2, x]
                    else r:= v[1, x];

  v[1, x]^.n := v[1, x]^.n+1;
  new (p); p^.n :=y; r^.a:=p; v[2, x]:=p;
  end;

ed:=nil;
for i := 1 to n do
  begin
  if chk[i]=false then
    begin
    chk[i]:= true;
    dfs(v[1, i], i);
    end;
  end;

p:= ed;
while p <> nil do
  begin
  write (g, p^.n, ' ');
  p:=p^.a;
  end;

close (f); close (g);
end.