Нехай дано орієнтований або неорієнтований граф без петель і кратних ребер. Потрібно перевірити, чи є він ациклічним, а якщо не є, то знайти будь-який цикл.
Вирішимо цю задачу за допомогою пошуку в глибину за O (M).
Алгоритм
Зробимо серію пошуків в глибину в графі. Тобто з кожної вершини, до якої ми ще жодного разу не приходили, запустимо пошук в глибину, який при вході в вершину буде фарбувати її в сірий колір, а при виході — у чорний. І якщо пошук в глибину намагається піти в сіру вершину, то це означає, що ми знайшли цикл (якщо граф неорієнтований, то випадки, коли пошук в глибину з якоїсь вершини намагається піти в предка, не рахуються).
Сам цикл можна відновити проходом по масиву предків.
Див. також
