Дан ориентированный граф. Требуется определить, есть ли в нем цикл. Обратите внимание на третий тест и подумайте, почему в нем нет цикла. Формат входных данных В первой строке вводится число n - количество вершин и m - количество ребер. ( 1 ≤slant n, m

Для определения наличия цикла в ориентированном графе можно использовать алгоритм обхода в глубину (DFS). Мы будем отслеживать состояние каждой вершины: не посещенная, посещенная и в процессе посещения. Если мы обнаружим вершину, которая уже находится в процессе посещения, это означает, что мы нашли цикл.

Вот пример реализации на Python:

1. : Мы используем список смежности для представления графа.
2. : Массив используется для отслеживания состояния каждой вершины:

• • не посещена
• • в процессе посещения
• • посещена

3. : Рекурсивная функция проверяет наличие цикла, помечая вершины в процессе обхода.
4. : Мы запускаем DFS для каждой непосещенной вершины.

• Для графа с вершинами 4 и рёбрами 4, где есть цикл, программа вернет .
• Для графа с 3 вершинами и 2 рёбрами без цикла, программа вернет .

Этот алгоритм работает за O(n + m), что подходит для ограничений задачи.