Определить, присутствует ли в графе цикл

Предмет: Это задание относится к предмету информатики. Раздел: теория графов (поиск циклов в графах). Также затрагиваются алгоритмы поиска циклов, такие как обход в глубину (DFS) для поиска циклов в ориентированных графах.

Объяснение задачи:

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

1. \(n\) — количество вершин графа (1 ≤ \(n\) ≤ \(10^5\)).
2. \(m\) — количество рёбер (1 ≤ \(m\) ≤ \(10^5\)).
3. Далее идет список рёбер графа в виде пар чисел \((u, v)\), где \(u\) — начальная вершина ребра, а \(v\) — конечная вершина.

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

• Если в графе нет цикла — нужно вывести "NO".
• Если в графе есть цикл, нужно вывести "YES" и перечислить вершины, которые образуют цикл.

Алгоритм решения:

1. Построение графа:
   • Мы можем представить граф в виде списка смежности: каждая вершина будет содержать список рёбер, ведущих к другим вершинам.
2. Поиск цикла:
   • Для поиска цикла используется алгоритм поиска в глубину (DFS).
   • При обходе графа мы можем отслеживать три состояния для каждой вершины:
     1. Не посещена (0).
     2. В процессе посещения (1) — если вершина уже "на пути" DFS, это может указывать на цикл.
     3. Посещена (2).
   • Если во время обхода встречаем вершину, которая находится "в процессе посещения" (статус 1), это означает, что был обнаружен цикл.
3. Отображение цикла:
   • Как только мы находим цикл, нам нужно восстановить путь этого цикла, собрав все вершины от текущей вершины до начала цикла.

Реализация:

python 
import sys
sys.setrecursionlimit(10**6)

def dfs(v, adj, visited, stack):
    visited[v] = 1  # В процессе посещения
    stack.append(v)
    for u in adj[v]:
        if visited[u] == 0:  # Если вершина еще не посещена
            if dfs(u, adj, visited, stack):
                return True
        elif visited[u] == 1:  # Найден цикл
            stack.append(u)
            return True
    visited[v] = 2  # Посещена
    stack.pop()
    return False

def find_cycle(n, adj):
    visited = [0] * (n + 1)
    stack = []
    for i in range(1, n + 1):
        if visited[i] == 0:
            if dfs(i, adj, visited, stack):  # Найден цикл в стеке
                cycle = []
                while stack:
                    v = stack.pop()
                    cycle.append(v)
                    if cycle[-1] == cycle[0] and len(cycle) > 1:
                        break
                cycle.reverse()
                return cycle
    return None

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)

cycle = find_cycle(n, adj)
if cycle:
    print("YES")
    print(" ".join(map(str, cycle)))
else:
    print("NO")

Пояснение:

1. Функция `dfs(v, adj, visited, stack)`:
   • Входит в вершину `v`, помечает её как "в процессе посещения". Это необходимо для отслеживания циклов.
   • Если находит вершину, которая уже "в процессе посещения" (то есть не завершила обход), это говорит о том, что найден цикл, и мы возвращаем его.
2. Функция `find_cycle(n, adj)`:
   • Проходит все вершины и начинает DFS с каждой непосещённой вершины. Как только находят цикл, он возвращается.
3. Основной блок:
   • Мы читаем граф, формируем его в списке смежности и ищем цикл.

Тест 1:

2
2
1 2
2 1

YES
1 2 1

Тест 2:

2
2
1 2
1 2

NO

Время работы и ограничения:

• Временная сложность: \(O(n + m)\), где \(n\) — количество вершин, \(m\) — количество рёбер.
• Пространственная сложность: \(O(n + m)\), так как используется список смежности и структуры для хранения статусов вершин.
• Задача укладывается в ограничения по времени (3 секунды) и памяти (256 МБ).

Мы имеем ориентированный граф с \(n\) вершинами и \(m\) рёбрами. Необходимо определить, присутствует ли в графе цикл. Цикл – это путь в графе, при котором можно вернуться в исходную вершину по рёбрам графа. Если цикл существует, нужно его вывести.