Выбор ответа Middle Графы: BFS и DFS обновлено
Порядок курсов
Вопрос
Курсы с зависимостями «чтобы взять A, нужно пройти B». Нужно проверить, можно ли пройти все. Какой подход?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Топологическая сортировка Кана: не все вершины обработаны значит цикл. Кан: считаем входящие степени, кладём в очередь курсы без зависимостей, «проходим» их и уменьшаем степени соседей.
Варианты ответа
- BFS от любого курса: если обошли все вершины, пройти можно
- Топологическая сортировка Кана: не все вершины обработаны значит циклправильный ответ
- Бинпоиск по числу курсов с проверкой, хватает ли зависимостей
- Жадно брать курс с наименьшим номером, пока курсы не кончатся
Разбор
Кан: считаем входящие степени, кладём в очередь курсы без зависимостей, «проходим» их и уменьшаем степени соседей. Если в итоге обработано меньше V вершин, остался цикл, и пройти всё нельзя. O(V + E).
- Простой BFS не проверяет порядок зависимостей.
- Бинпоиск не к месту.
- Наименьший номер не учитывает зависимости.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.