олимпиадники-информатики

Дан граф, состоящий из n вершин и m ребер. Далее даны описания ребер (откуда и куда). Требуется расположить вершины так, чтобы все ребра совпадали по направлениям.

Например дан граф из 6 вершин



Тогда мы можем расположить вершины в такое порядке: 5 2 7 1 3 6. Почему так? Потому что: 5 --> 2, 2 --> 7, 5 --> 1, 1 --> 3, 1 --> 6, 3 --> 6. Все стрелки --> получились одинаковыми, а значит мы отсортировали граф топологически.

Реализация поиском глубиной

Перебираем все вершины и смотрим, что если она не помеченная (used массив меток), тогда из нее пускаем глубину

for i:=1 to n do
  if not(used[i]) then dfs(i);

Рассмотрим dfs. Думаю, я не буду все расписывать, ведь всё указано в пунктах выше, разве что некоторые моменты

 
procedure dfs(v:longint);
var i:longint;
begin
  used[v]:=false; //помечаем вершину, типа мы здесь были
  for i:=1 to n do
    if (not(used[i])) and (g[v,i]=1) //если мы не были в этой вершине и есть путь из вершины v в нашу
      then
        begin
          parent[i]:=v; //предком для нашей вершины является вершина v, т.е. мы пришли из неё
          dfs(i); //глубиной идем от нашей вершины
        end;
  inc(cnt); //увеличиваем счетчик
  dag[cnt]:=v; //в массив тоположки кидаем нашу вершину v
end;

Ну и сам вывод массива вершин, топологически отсортированного

for i:=cnt downto 1 do
  write(dag[i],' ');

Сообщение отредактировал Санек: 20 ноября 2012 - 17:25