Код Senior Графы: BFS и DFS обновлено
Можно ли пройти все курсы
Условие
Пары [курс, требуется] задают зависимости. Можно ли пройти все n курсов?
Примеры
canFinish(2, [[1, 0]]) // true
canFinish(2, [[1, 0], [0, 1]]) // false
canFinish(3, []) // true
Как подойти
Переформулировка - половина решения: «можно ли пройти все курсы» это «нет ли цикла в графе зависимостей». Алгоритм Кана даёт ответ бесплатно, сравнением числа обработанных вершин с общим. Тот же вопрос возникает при разрешении зависимостей модулей и задач сборки.
Подсказки: 2
- Задача сводится к поиску цикла в ориентированном графе.
- Топологическая сортировка обработает все вершины, только если цикла нет.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.