3. Поиск в глубину

Алгоритм топологической сортировки

Задача топологической сортировки ориентированного графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любая дуга вела от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.

var 
  s:array[1..1000] of integer; { топологически 
      упорядоченная последовательность вершин }
  u:array[1..1000] of integer; { флаги сортировки:
    0 - вершина не упорядочивалась,
    1 - упорядочена, 
    -1 - в процессе упорядочения }
  d:array[1..1000,1..1000] of integer; { матрица связей в графе, 
     d[i,j]=1 если есть дуга из вершины i в j }
  n, { количество вершин }
  m, { количество дуг }
  i,j,k:integer;

Алгоритм топологической сортировки

function topsort(i:integer):boolean;
var j:integer;
begin
  if u[i]<>0 then
  begin
    topsort:=u[i]=1; { если уже упорядочена - успех, иначе - неудача }
    exit;
  end;
  u[i]:=-1; { начали упорядочивать вершину i }
  for j:=1 to n do
    if d[i,j]<>0 then
      if not topsort(j) then
      begin
        topsort:=false; { неудача - есть цикл }
        exit;
      end;
  inc(k);
  s[k]:=i;
  u[i]:=1; { вершина i упорядочена }
  topsort:=true; { успех }
end;

Ввод данных

read(n,m);
for i:=1 to m do { ввод дуг графа }
begin
  read(j,k);
  d[j,k]:=1;
end;

Сортировка и вывод результата

k:=0;
for i:=1 to n do
  if not topsort(i) then
  begin
    writeln('Impossible');
    halt;
  end;
for i:=1 to k do { вывод упорядоченной последовательности }
  write(' ',s[i]);