Course Schedule
Есть numCourses курсов, пронумерованных от 0 до numCourses-1. Каждая пара [a, b] в prerequisites означает, что нужно закончить курс b, прежде чем начинать курс a. Верните true, если существует такой порядок, который позволяет пройти все курсы, и false, если такого порядка нет.
Функция
- numCoursesinteger
- количество курсов
- prerequisitesinteger-2d-array
- пары [a, b], каждая из которых означает, что курс b предшествует курсу a
- Возвращаетboolean
- true, если каждый курс можно завершить, иначе false
Ограничения
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Каждая пара
[a, b]удовлетворяет условию0 ≤ a, b < numCourses. - Ни одна пара не встречается дважды.
- Пара может дважды указывать один и тот же курс:
[a, a]. Этому курсу сначала нужен он сам, поэтому его невозможно пройти.
Примеры
- Ввод
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Вывод
- true
- Пояснение
- У курса 0 нет предварительных требований, поэтому ты проходишь его первым. Это открывает возможность пройти курс 1, который открывает возможность пройти курсы 2 и 3, так что порядок 0, 1, 2, 3 подходит.
- Ввод
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Вывод
- false
- Пояснение
- Курс 0 ждёт курс 2, курс 2 ждёт курс 1, а курс 1 ждёт курс 0. Все три ждут друг друга в цикле, поэтому ни один из них не может начать первым.
Дополнительный вопрос
За один семестр можно пройти любое количество курсов, если предварительные требования для каждого курса были выполнены в предыдущих семестрах. Каково минимальное количество семестров, за которое можно пройти все курсы?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Изобрази каждый курс точкой, а каждую пару
[a, b]— стрелкой отbкa. Какая фигура на этом рисунке сделает невозможным завершение курсов?Цикл из стрелок. Каждый курс в цикле ожидает другой курс из того же цикла, поэтому ни один из них не может идти первым. Вопрос в том, есть ли в графе цикл.
Посчитай, сколько обязательных предварительных курсов ещё ожидает каждый курс. Добавь в очередь курсы, для которых это количество равно 0, и каждый раз, когда берёшь один из них, уменьши количество для каждого курса, который его ожидает. Если в очередь когда-либо попадёт меньше курсов, чем
numCourses, значит, есть цикл.
Решение
Нарисуй стрелку b → a для каждой пары [a, b]. Все курсы можно закончить тогда и только тогда, когда в этом графе с V = numCourses узлами и E = prerequisites.length стрелками нет циклов. Алгоритм Кана проверяет это так, как планирует студент: продолжай проходить курсы, все необходимые для которых уже пройдены, и проверь, будут ли пройдены все курсы.
Проходите каждый бесплатный курс, раунд за раундом
Верно, но не успевает на самых больших тестах
Идея
В каждом раунде берите все ещё не пройденные курсы, для которых уже пройдены все необходимые курсы. Остановитесь, когда раунд не пройдёт ни одного курса, и ответьте true, если пройдены все курсы. Раунд не проходит ни одного курса только тогда, когда каждый оставшийся курс зависит от другого оставшегося курса, то есть есть цикл.
В каждом раунде заново проверяются все пары и все курсы, но может быть пройден всего один курс. Цепочка из 5,001 курса среди 100,000 курсов требует более 5,000 раундов: около 5 × 10^8 проверок.
Алгоритм
- Отметьте каждый курс как непройденный.
- Отметьте курс как заблокированный, если какая-либо пара задаёт для него непройденную предпосылку.
- Пройдите каждый курс, который ещё не пройден и не заблокирован.
- Если за раунд ничего не пройдено, остановитесь; иначе вернитесь к шагу 2.
- Верните true, если пройдены все курсы.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCoursesПоиск в глубину с тремя состояниями
Идея
Поиск в глубину находит цикл, отслеживая путь, по которому он проходит. Задай каждому курсу одно из трёх состояний: не посещён, на пути, завершён. Следуй по стрелкам от курса к курсам, которые его ожидают. Отмечай курс как находящийся на пути, когда входишь в него, и как завершённый, когда исследованы все его стрелки.
Стрелка к курсу, находящемуся на пути, замыкает цикл: верни false. Стрелка к завершённому курсу безопасна, потому что всё достижимое из него уже проверено и не содержит циклов, поэтому повторное достижение курса само по себе не является циклом. Каждый курс посещается один раз, и каждая стрелка проходится один раз: O(V + E).
Алгоритм
- Постройте для каждого курса список курсов, которые его ждут.
- Для каждого курса, который ещё не посещён, отметьте его в пути и поместите в стек.
- Посмотрите на верхний элемент стека. Если от него не осталось стрелок, отметьте его как завершённый и извлеките из стека; иначе перейдите по следующей стрелке.
- Если стрелка ведёт к курсу, который находится в пути, верните false. Если она ведёт к непосещённому курсу, отметьте этот курс в пути и поместите его в стек.
- Когда все курсы будут завершены, верните true.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return TrueАлгоритм Кана
Идея
Курс становится доступным в один момент: когда пройдена его последняя обязательная дисциплина. Поэтому храните входящую степень каждого курса — количество обязательных дисциплин, которые ещё нужно пройти, — и поместите в очередь все курсы, у которых это количество равно 0. Прохождение курса уменьшает количество для каждого курса, который от него зависит; когда количество достигает 0, курс добавляется в очередь. В первом примере начальные значения равны 0, 1, 1, 1: прохождение 0 делает доступным 1, а прохождение 1 — 2 и 3. Каждый курс добавляется в очередь один раз, и для каждой пары курсов одно значение уменьшается один раз: O(V + E).
Если очередь опустеет, пока курс a ещё не пройден, его значение больше 0, значит, не пройдена и какая-то обязательная дисциплина для a, и так далее. При таком обходе обязательно встретится уже посещённый курс: это цикл. И наоборот, каждый курс в цикле зависит от другого курса в этом же цикле, поэтому ни один не может быть пройден первым. Порядок, в котором курсы покидают очередь, задаёт допустимое расписание.
Алгоритм
- Для каждой пары [a, b] добавьте a в список курсов, ожидающих b, и увеличьте входящую степень a на 1.
- Поместите в очередь каждый курс с входящей степенью 0.
- Извлеките курс из очереди и посчитайте его. Уменьшите входящую степень каждого курса, который его ожидает, и добавьте в очередь каждый курс, входящая степень которого стала равна 0.
- Когда очередь опустеет, верните результат проверки, равно ли количество
numCourses.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
Ловушки и крайние случаи
- Путаница с направлением.
[a, b]означает, что сначала идёт b: стрелка направлена от b к a, а входящая степень a увеличивается. - Забыть о курсах, которые не встречаются ни в одной паре. При
numCourses = 5и единственной паре[4, 3]курсы 0, 1 и 2 тоже должны изначально попасть в очередь. - Использование двух состояний вместо трёх при поиске в глубину. В ромбовидном графе 0 → 1, 0 → 2, 1 → 3, 2 → 3 до курса 3 доходят дважды, и он кажется циклом, если отслеживать только «посещённые» узлы.
- Рекурсивный обход цепочки из 5 000 курсов: глубина в 5 000 вызовов превышает стандартный лимит Python в 1 000.
- Возвращать true, когда очередь опустела, не проверив, что были пройдены
numCoursesкурсов. Во втором примере программа вернула бы true.
Частые вопросы3
Какова временная сложность задачи о расписании курсов?
O(V + E), где V — количество курсов, а E — количество пар; можно использовать алгоритм Кана или поиск в глубину. Каждая пара считывается один раз, и каждый курс обрабатывается один раз. Списки и счётчики занимают O(V + E) памяти.
Следует ли использовать BFS или DFS для расписания курсов?
Оба алгоритма работают за O(V + E). Алгоритм Кана, вариант с поиском в ширину, не требует беспокоиться о глубине рекурсии и позволяет получить корректный порядок курсов. Поиск в глубину с тремя состояниями — естественный выбор, если нужно также сообщить о цикле, поскольку его образуют курсы в стеке.
Что такое топологическая сортировка?
Порядок узлов ориентированного графа, в котором каждая стрелка направлена вперёд; здесь — порядок, в котором каждая обязательная дисциплина предшествует курсу, которому она нужна. Такой порядок существует тогда и только тогда, когда в графе нет циклов, и порядок, в котором алгоритм Кана выбирает курсы, является таким порядком. Задача Course Schedule спрашивает, существует ли такой порядок.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def canFinish(numCourses, prerequisites):
# Напишите код здесьТест #1
Тест #2
Аргументы
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Ожидаемый вывод
true