Программа курса:
Внимание! Решать задачи может только авторизованный
пользователь. Пройдите регистрацию на сайте.
Задача 11: Все пути от источника к цели
Напишите определение функции allPathsSourceTarget(graph), которая принимает ориентированный ациклический граф (DAG) в виде списка смежности graph и возвращает все возможные пути из узла 0 в узел n-1.
Граф задан следующим образом: graph[i] — это список всех узлов, в которые можно попасть из узла i (то есть существует направленное ребро из узла i в узлы graph[i][j]).
Примеры
Пример 1:
Ввод: graph = [[1,2],[3],[3],[]]
Вывод: [[0,1,3],[0,2,3]]
Объяснение:
Существует два пути: 0 -> 1 -> 3 и 0 -> 2 -> 3.
Пример 2:
Ввод: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Вывод: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
Объяснение:
Существует несколько путей, например:
- 0 -> 4
- 0 -> 3 -> 4
- 0 -> 1 -> 3 -> 4
- 0 -> 1 -> 2 -> 3 -> 4
- 0 -> 1 -> 4
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии