В 2008 обсуждалась эта тема, но уже закрыта.
Вот последнее сообщение:
"От: Eugene Kilachkoff
Дата: 09.04.08 17:45
Здравствуйте, Beam, Вы писали:

B>
B>Наличие циклов в графе можно определить с помощью эффективного алгоритма. Алгоритм может быть реализован как для матричного, так и для спискового способа представления графа.

B>Принцип выделения циклов следующий. Если вершина имеет только входные или только выходные дуги, то она явно не входит ни в один цикл. Можно удалить все такие вершины из графа вместе со связанными с ними дугами. В результате появятся новые вершины, имеющие только входные или выходные дуги. Они также удаляются. Итерации повторяются до тех пор, пока граф не перестанет изменяться. Отсутствие изменений свидетельствует об отсутствии циклов, если все вершины были удалены. Все оставшиеся вершины обязательно принадлежат циклам.


Чисто практическое замечание: это будет работать, если имеется способ перебора элементов графа, отличный от переходов по дугам. Например, в случае зацикленного двусвязного списка -- облом."

Чисто теоретическое замечание: Утверждение "Все оставшиеся вершины обязательно принадлежат циклам." не верно.
Контр-пример: Два кольца соединённые путём длины 2 и более. Внутренние узлы такого пути не входят в циклы.