Найти цикл в ориентированном графе
Графы
Сложная
Дан ориентированный граф: n вершин, список рёбер edges. Если в графе есть цикл, верните вершины ОДНОГО из циклов по порядку обхода (первая вершина повторяется в конце НЕ нужно - только сами вершины цикла ровно по одному разу). Если циклов нет, верните пустой список.
Используйте DFS с тремя цветами вершин (белый/серый/чёрный): ребро в серую вершину - это цикл, который можно восстановить по стеку рекурсии.
Сигнатура функции
find_cycle(n: int, edges: list[list[int]]) -> list[int]
Примеры
| Вход | Ожидаемый результат |
| [3, [[0, 1], [1, 2], [2, 0]]] | [0, 1, 2] |
| [3, [[0, 1], [1, 2]]] | [] |
1решили
1пытались
100%успешность
Войдите, чтобы решить →