Поиск циклов в орграфе

[Usr]

Добрый день! Помогите, пожалуйста, разобраться с задачей.

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

В начале помечаю все вершины как WHITE(не посещены). Потом выбираем незакрашенную вершину, перекрашиваем ее в GREY(посещена, но не отработана) и вызываем поиск в глубину. Вершина закрашивается в BLACK, когда у мы вернулись в нее из рекурсии и у нее больше нет непосещенных вершин. При этом, если при вызове DFS(v) смежная вершина c ней вершина -GREY, то мы вернулись в неотработанную вершину, значит, найден цикл.

Проблема заключается в том, что если у какой-то вершины больше нет смежных, она закрашивается в черный. При этом, если существует какая-то другая дуга в эту вершину, то, поскольку она закрашена, этот путь не определяется как цикл. (см. прикрепленное изображение - вершина 3 закрашивается, путь 1-2-4-3-1 не будет циклом). Я уж пробовал не закрывать вершину, если в нее есть хотя бы 1 дуга, но тогда возникает проблема с определением момента, когда она отработана (закраска в BLACK)..

Подскажите, как можно изменить логику, чтобы учесть такой вариант.. Слышал что-то про проверку на наличие обратной дуги, но в таком случае ведь придется определить, является ли открываемая вершина предком данной.. Но это придется перебрать всех потомков этой вершины и сравнить их со всеми предками?

Заранее спасибо..