Коротко — использовать три состояния вершин (белая/серая/чёрная) или стек рекурсии; при обнаружении ребра в серую вершину — найден ориентированный цикл. Для восстановления цикла хранить указатель на родителя или стек текущего пути.
Модификация DFS (три состояния + восстановление через parent):
function DFS(v):
state[v] := GRAY // вошли в вершину, в стеке рекурсии
for u in neighbors(v):
if state[u] == WHITE:
parent[u] := v
DFS(u)
else if state[u] == GRAY:
// найдено обратное ребро v -> u => есть цикл
reconstruct_cycle(v, u)
state[v] := BLACK // выход из вершины
Реконструкция цикла с parent:
cycle := []
x := v
while x != u:
cycle.prepend(x)
x := parent[x]
cycle.prepend(u) // замыкаем цикл
Альтернатива (стек): при входе в вершину выполнять push(v) в стек пути, при выходе делать pop(). Если встречаем ребро v->u и u уже в стеке, то цикл — это все вершины от u до вершины на вершине стека; собрать их, пройдя стек сверху вниз до u.
Структуры данных и сложность:
- state[] (size $|V|$) — три состояния (WHITE/GRAY/BLACK) или \{0,1,2\};
- parent[] (size $|V|$) или стек пути (максимум глубина рекурсии $|V|$);
- при обнаружении цикл восстанавливается за время пропорционально длине цикла $k$ (операций $\Theta (k)$).
Общая сложность алгоритма: $\Theta (|V|+|E|)$.