Бесконтурные орграфы., Индекс цепной сложности. Опции

[Nuty]

Помогите пожалуйста решить задачу по теории графов: необходимо найти самый длинный путь в бесконтурном орграфе.

Сообщение отредактировано: Nuty - 5.11.2006 21:21

[Michael_Rybak]

Обходим граф поиском в глубину, запоминая ответ для каждой вершины. Примерно так:

var ans: array[1..n] of longint;

function Search(i: longint): longint;
  var best: longint;
begin
  if ans[i] = -1 then begin (* впервые посещена вершина i; выбираем, куда из нее лучше идти *)
    ans[i] := 0;
    для всех вершин j, в которые есть ребро из i:
      ans[i] := max(ans[i], 1 + Search(j));
  end;
  Search := ans[i];
end;

begin
 ...
 for i := 1 to n do
   ans[i] := -1; //ни одна вершина еще не посещена

 longest := 0;
 for i := 1 to n do
   longest := max(longest, Search(i));

  Writeln(longest);
end.

Этот полупсевдокод выводит количество ребер в самом длинном пути, работает за O(V+E). Как построить сам путь - додумаешь. Не получится - разберись с этим, и приходи.