Топологическая сортировка
Графы
Экстремальная
Дан ориентированный ациклический граф (DAG) в виде списка смежности graph (graph[i] — рёбра из i). Верните один из вариантов топологической сортировки: на каждом шаге среди вершин без невыполненных зависимостей выбирайте вершину с наименьшим номером (алгоритм Кана).
Сигнатура функции
topological_sort(graph: list[list[int]]) -> list[int]
Примеры
| Вход | Ожидаемый результат |
|---|
| [[[1, 2], [3], [3], []]] | [0, 1, 2, 3] |
| [[[1], [2], [3], []]] | [0, 1, 2, 3] |
1решили
1пытались
100%успешность
Войдите, чтобы решить →