Cod sursa(job #843351)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 27 decembrie 2012 20:59:28
Problema Sortare topologica Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.57 kb
program sortare_topologica;
  type lista=^celula;
       celula=record
                info:longint;
                next:lista;
              end;
  var f1,f2:text;
      n,m,i,x,y:longint;
      a:array [1..50000] of lista;
      b:array [1..50000] of longint;
      r,r2,coada,v:lista;

begin
  assign(f1,'sortaret.in');
  reset(f1);
  assign(f2,'sortaret.out');
  rewrite(f2);
  readln(f1,n,m);
  for i:=1 to n do
    begin
      new(a[i]);
      a[i]^.info:=0;
      a[i]^.next:=nil;
    end;
  for i:=1 to m do
    begin
      readln(f1,x,y);
      new(r);
      r^.info:=y;
      r^.next:=a[x]^.next;
      a[x]^.next:=r;
      inc(b[y]);
    end;
  new(coada);
  i:=1;
  while b[i]<>0 do inc(i);
  coada^.info:=i;
  coada^.next:=nil;
  inc(i); v:=coada;
  while i<=n do
    begin
      if b[i]=0 then
        begin
          new(r);
          r^.info:=i;
          r^.next:=nil;
          v^.next:=r;
          v:=r;
        end;
      inc(i);
    end;
  while coada<>nil do
    begin
      write(f2,coada^.info,' ');
      r:=a[coada^.info]^.next;
      while r<>nil do
        begin
          dec(b[r^.info]);
          if b[r^.info]=0 then
                            begin
                              new(r2);
                              r2^.info:=r^.info;
                              r2^.next:=nil;
                              v^.next:=r2;
                              v:=r2;
                            end;
          r:=r^.next;
        end;
      coada:=coada^.next;

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