Решение задачи #11. Python Яндекс CodeRun, Поиск цикла

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Название задачи: Поиск цикла.
Статус решения: "Решено".

Условие задачи:
Дан неориентированный граф. Требуется определить, есть ли в нем цикл, и, если есть, вывести его.

Формат ввода:
В первой строке дано одно число n — количество вершин в графе ( 1  ≤≤ n ≤≤  500 ). Далее в n строках задан сам граф матрицей смежности.

Формат вывода:
сли в иcходном графе нет цикла, то выведите «NO». Иначе, в первой строке выведите «YES», во второй строке выведите число k — количество вершин в цикле, а в третьей строке выведите k различных чисел — номера вершин, которые принадлежат циклу в порядке обхода (обход можно начинать с любой вершины цикла). Если циклов несколько, то выведите любой.

Python

import sys

def main():
    # Чтение входных данных
    n = int(input())  # Количество вершин в графе
    graph = [list(map(int, input().split())) for _ in range(n)]  # Матрица смежности графа

    # Функция для поиска цикла с использованием DFS
    def find_cycle(graph, n):
        visited = [0] * n  # Массив для отслеживания состояния вершин (0 - не посещена, 1 - в процессе, 2 - завершено)
        parent = [-1] * n  # Массив для хранения предков вершин
        cycle_start = -1  # Начало цикла
        cycle_end = -1  # Конец цикла

        # DFS-обход графа
        def dfs(v):
            nonlocal cycle_start, cycle_end
            visited[v] = 1  # Вершина в процессе обработки
            for u in range(n):
                if graph[v][u]:  # Если есть ребро между v и u
                    if visited[u] == 0:  # Если вершина u не посещена
                        parent[u] = v
                        if dfs(u):  # Рекурсивный вызов для u
                            return True
                    elif visited[u] == 1 and parent[v] != u:  # Обнаружен цикл
                        cycle_start = u
                        cycle_end = v
                        return True
            visited[v] = 2  # Вершина полностью обработана
            return False

        # Запускаем DFS для каждой вершины
        for i in range(n):
            if visited[i] == 0:  # Если вершина ещё не посещена
                if dfs(i):  # Если найден цикл
                    break

        # Если цикл найден, восстанавливаем его
        if cycle_start != -1:
            cycle = []  # Список для хранения вершин цикла
            current = cycle_end
            while current != cycle_start:
                cycle.append(current + 1)  # Добавляем вершины в цикл (нумерация с 1)
                current = parent[current]
            cycle.append(cycle_start + 1)  # Добавляем начальную вершину цикла
            cycle.reverse()  # Переворачиваем список, чтобы получить правильный порядок
            return cycle
        return None

    # Поиск цикла
    cycle = find_cycle(graph, n)

    # Вывод результата
    if cycle is None:
        print("NO")  # Цикл не найден
    else:
        print("YES")  # Цикл найден
        print(len(cycle))  # Количество вершин в цикле
        print(*cycle)  # Вершины цикла


if __name__ == '__main__':
    main()

Объяснение кода

1. Чтение входных данных
Мы считываем количество вершин n и матрицу смежности графа.
Матрица смежности — это двумерный массив размером n×n, где элемент graph[i][j] равен 1, если между вершинами i и j есть ребро, и 0, если нет.

2. Поиск цикла с помощью DFS
Для поиска цикла используется алгоритм обхода в глубину (DFS).
Мы поддерживаем три состояния вершин:
0: вершина ещё не посещена.
1: вершина находится в процессе обработки (в стеке DFS).
2: вершина полностью обработана.
Если во время обхода мы встречаем вершину, которая уже находится в процессе обработки (visited[u] == 1), то это означает, что найден цикл.

3. Восстановление цикла
Когда цикл обнаружен, мы сохраняем его начало (cycle_start) и конец (cycle_end).
Затем, используя массив parent, который хранит предков вершин, мы восстанавливаем путь от cycle_end до cycle_start.
После этого добавляем cycle_start в конец списка и переворачиваем его, чтобы получить правильный порядок обхода.

4. Вывод результата
Если цикл найден, выводим "YES", количество вершин в цикле и сами вершины.
Если цикл не найден, выводим "NO".

Пример работы программы:
Ввод:
4
0 1 1 0
1 0 1 0
1 1 0 0
0 0 0 0

Вывод:
YES
3
1 2 3

Объяснение:
Граф содержит цикл из трёх вершин: 1, 2 и 3.
Порядок обхода цикла может быть любым, например: 1 -> 2 -> 3.

Пример без цикла:
Ввод:
3
0 1 0
1 0 0
0 0 0

Вывод:
NO

Объяснение:
Граф не содержит циклов, так как все вершины соединены линейно.

Детали реализации:
Сложность алгоритма :
Временная сложность: O(N2), где N — количество вершин. Это связано с тем, что мы используем матрицу смежности.
Пространственная сложность: O(N2) для хранения матрицы смежности и O(N) для массивов visited и parent.

Ограничения:
Код работает корректно при N≤500, что соответствует ограничениям задачи.
Алгоритм укладывается в ограничения по времени и памяти.

Обработка граничных случаев:
Если граф пустой (нет рёбер), программа выведет "NO".
Если граф состоит из одной вершины, программа также выведет "NO", так как цикл требует хотя бы двух вершин.

Источник решения: hahai.com