циклы в графе, есть ли цикл в орентированном графе? Опции

[Bard]

У меня тут одна задачка в которой нужно найти есть ли цикл в графе? Никакие поисковики не помогли. Может вы знаете алгоритм? Заранее большое спасибо.

[volvo]

Что, Гугл вот про эту страничку не знает: http://guap.ru/dept04/caf46/textbooks/str_alg/index4.htm ?

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