7. Есть ли цикл?

Задача

Дан ориентированный граф. Необходимо определить, содержит ли он цикл.

Входные данные

В первой строке указаны числа $n$ и $m$ ($1 \leqslant n, m \leqslant 10^5$) — количество вершин и рёбер. В следующих $m$ строках записаны пары $u$, $v$ ($1 \leqslant u, v \leqslant n$) — ориентированные рёбра графа.

Выходные данные

Выведите 1, если в графе есть цикл, и 0 иначе.

Примеры

стандартный ввод      стандартный вывод
4 4                    1
1 2
2 3
3 4
4 1

3 2                    0
1 2
1 3

Ограничения

  • Время: 1 секунда
  • Память: 256 мегабайт
Редакционный разбор Используем DFS с раскраской вершин в три состояния: `0` — не посещена, `1` — сейчас в стеке рекурсии, `2` — полностью обработана. Когда из вершины идём по ребру в вершину цвета `1`, найден цикл. Если обход завершился без таких ситуаций, граф ацикличен. Альтернативно можно выполнить топологическую сортировку алгоритмом Кана: если удаётся вынести все вершины, цикла нет, иначе — есть. Обе реализации работают за $O(n + m)$.

Mentioned by