Программа курса:
Внимание! Решать задачи может только авторизованный
пользователь. Пройдите регистрацию на сайте.
Задача 13: Нахождение возможных безопасных состояний
Напишите определение функции eventualSafeNodes(graph), которая принимает на вход список смежности graph. Этот список описывает направленный граф, где graph[i] — это список всех вершин, в которые есть ребро из вершины i.
Функция должна возвращать список всех "безопасных узлов" графа, отсортированных в порядке возрастания. Узел считается безопасным, если любой возможный путь, начинающийся с этого узла, приводит либо к конечному узлу, либо к другому безопасному узлу. Узел называется конечным, если из него нет исходящих ребер.
Примеры
Пример 1:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation:
- Узлы 5 и 6 являются конечными, так как у них нет исходящих ребер.
- Каждый путь, начинающийся с узлов 2, 4, 5 или 6, приводит только к узлам 5 или 6. Эти узлы являются безопасными.
Пример 2:
Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:
- Узел 4 является конечным, так как у него нет исходящих ребер.
- Все пути, начинающиеся с узла 4, приводят только к узлу 4. Он является безопасным.
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии