Course Schedule: можно ли пройти все курсы, если часть зависит друг от друга

Классический вопрос на графы: дано число курсов и список пар [a, b], означающих «чтобы пройти a, нужно сначала пройти b». Нужно ответить, можно ли пройти все курсы — то есть нет ли цикла в графе зависимостей.

Задачу решают и DFS с тремя цветами, и алгоритм Кана. Разберём Кана: он явно показывает, какие курсы уже доступны после выполнения зависимостей.

Идея: считаем indegree (сколько зависимостей у каждого курса), кладём в очередь курсы с indegree = 0 — те, которые можно пройти прямо сейчас без предпосылок. Берём курс из очереди, «проходим» его, уменьшаем indegree у всех курсов, которые от него зависели. Если у кого-то indegree стал 0 — он тоже встаёт в очередь.

fun canFinish(numCourses: Int, prerequisites: Array): Boolean { val indegree = IntArray(numCourses) val graph = Array(numCourses) { mutableListOf() } for ((course, prereq) in prerequisites) { graph[prereq].add(course) indegree[course]++ } val queue = ArrayDeque() for (i in 0 until numCourses) { if (indegree[i] == 0) queue.add(i) } var processed = 0 while (queue.isNotEmpty()) { val cur = queue.removeFirst() processed++ for (next in graph[cur]) { indegree[next]-- if (indegree[next] == 0) queue.add(next) } } return processed == numCourses }

Если в конце обработано меньше курсов, чем всего — значит, остался цикл: курсы внутри него никогда не получат indegree = 0, потому что зависят друг от друга по кругу. В варианте Course Schedule II нужно вернуть порядок прохождения: для этого добавляйте каждый извлечённый из очереди курс в список результата. Вернуть порядок можно, только если обработаны все курсы.

Оба подхода работают за O(V + E). В DFS порядок тоже можно получить: добавлять вершины после обхода зависимых и затем развернуть список. Обнаруженный цикл делает топологический порядок невозможным.

Тренажёр: 1900+ вопросов и задач, мок с таймером, план повторов

senior·base — что спрашивают на самом деле

В этом посте были ссылки, но мы их удалили по правилам Сетки