Course Schedule

Q: Какова временная сложность задачи Course Schedule?

O(V + E), где V — количество курсов, а E — количество пар, при использовании алгоритма Кана или поиска в глубину. При построении списков каждая пара считывается один раз, каждый курс попадает в очередь не более одного раза, а каждая пара один раз уменьшает один счетчик. Для списков и счетчиков требуется O(V + E) памяти.

Q: Почему оставшийся курс в алгоритме Кана означает, что в графе есть цикл?

Курс остаётся только в том случае, если его счётчик так и не достиг 0, а значит, остаётся и хотя бы один из его обязательных предварительных курсов. Проследи за этим ожиданием от курса к курсу: каждый шаг ведёт к другому оставшемуся курсу, и поскольку число курсов конечно, в какой-то момент путь должен вернуться к уже посещённому курсу. Участок между двумя посещениями образует цикл.

Q: Что использовать для расписания курсов: BFS или DFS?

Оба алгоритма работают за O(V + E). Алгоритм Кана, вариант с поиском в ширину, не требует беспокоиться о глубине рекурсии и сразу выдаёт допустимый порядок курсов. Поиск в глубину с тремя состояниями работает так же быстро и является естественным выбором, когда нужно также сообщить о цикле, поскольку его образуют курсы в стеке.

Q: Что такое топологическая сортировка?

Порядок узлов ориентированного графа, при котором каждая стрелка направлена вперёд; здесь — порядок курсов, в котором каждый курс, являющийся предварительным условием, стоит раньше курса, которому он необходим. Такой порядок существует тогда и только тогда, когда в графе нет циклов, и порядок, в котором алгоритм Кана выбирает курсы, — один из таких порядков. Задача Course Schedule спрашивает, существует ли топологический порядок.

СреднеТопологическая сортировка Графы

+10

Есть numCourses курсов, пронумерованных от 0 до numCourses-1. Каждая пара [a, b] в prerequisites означает, что нужно закончить курс b, прежде чем начинать курс a. Верните true, если существует порядок, в котором можно закончить все курсы, и false, если такого порядка нет.

Функция

canFinish(numCourses: integer, prerequisites: integer-2d-array) → boolean

numCoursesinteger: количество курсов
prerequisitesinteger-2d-array: пары [a, b], каждая из которых означает, что курс b предшествует курсу a
Возвращаетboolean: true, если все курсы можно завершить, иначе false

Ограничения

1 ≤ numCourses ≤ 10⁵
1 ≤ prerequisites.length ≤ 5000
Для каждой пары [a, b] выполняется условие 0 ≤ a, b < numCourses.
Ни одна пара не встречается дважды.
Пара может дважды указывать один и тот же курс: [a, a]. Сначала этому курсу нужен он сам, поэтому его нельзя пройти.

Примеры

Ввод: numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
Вывод: true
Пояснение: Для курса 0 нет предварительных требований, поэтому сначала пройдите его. Это освобождает курс 1, а курс 1 открывает доступ к курсам 2 и 3, поэтому порядок 0, 1, 2, 3 подходит.

+20 скрытых тестов при отправке

Дополнительный вопрос

В одном семестре может быть сколько угодно курсов, если предварительные требования для каждого курса были выполнены в предыдущих семестрах. Каково наименьшее количество семестров, за которое можно пройти все курсы?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Преобразуйте пары в ориентированный граф с V = numCourses узлами и E = prerequisites.length рёбрами, по одной стрелке b → a для каждой пары [a, b]. Все курсы можно закончить тогда и только тогда, когда в графе нет циклов. Алгоритм Кана решает эту задачу так, как стал бы планировать студент: продолжать проходить курсы, все предварительные требования которых уже выполнены, и посмотреть, закончатся ли сначала курсы или доступные варианты.

Проходи каждый бесплатный курс, раунд за раундом

Верно, но не успевает на самых больших тестах

Идея

Планируй так же, как студент. В каждом раунде просматривай каждый курс, который ты ещё не проходил. Если все его предварительные требования выполнены, проходи его. Повторяй, пока в каком-нибудь раунде не будет пройдено ни одного курса. Если к этому моменту пройдены все курсы, ответ — true.

Почему остановившийся раунд означает false: когда в раунде не пройдено ни одного курса, у каждого оставшегося курса есть предварительное требование, которое тоже осталось невыполненным. Начни с любого оставшегося курса и переходи к одному из его невыполненных предварительных требований. Ты не исчерпаешь возможные шаги, а курсов конечное число, поэтому вернёшься к курсу, который уже посещал. Это цикл, и курсы в нём будут вечно ждать друг друга.

Этот метод корректен, но в каждом раунде он заново просматривает все пары и все курсы, а за раунд можно пройти всего один курс. Цепочка из 5,001 курса, каждый из которых требует прохождения предыдущего, занимает более 5,000 раундов; среди 100,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. Стрелка к обработанному курсу безопасна, поскольку всё достижимое из него уже проверено и циклов там нет, поэтому пропустите его. Каждый курс посещается один раз, и по каждой стрелке проходят один раз.

Двух состояний недостаточно. В ромбе 0 → 1, 0 → 2, 1 → 3, 2 → 3 поиск достигает курса 3 во второй раз через 2, но к тому времени 3 уже обработан, а не находится на пути, и цикла нет. Только стрелка обратно на текущий путь замыкает цикл.

Напишите поиск с собственным стеком и храните для каждого курса позицию его следующей непроверенной стрелки. Рекурсивная версия короче, но цепочка из 5 000 курсов потребовала бы 5 000 уровней вызовов.

Алгоритм

Постройте для каждого курса список курсов, которые его ожидают.
Для каждого курса, который ещё не посещён, отметьте его в пути и поместите в стек.
Посмотрите на вершину стека. Если от неё не осталось стрелок, отметьте её как завершённую и извлеките из стека; иначе перейдите по следующей стрелке.
Если стрелка ведёт к курсу, который уже есть в пути, верните 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 по 3 равны 0, 1, 1, 1. Прохождение курса 0 уменьшает счётчик курса 1 до 0; прохождение курса 1 уменьшает счётчики курсов 2 и 3 до 0; пройдены все четыре курса, поэтому ответ — true. Каждый курс попадает в очередь не более одного раза, и счётчик уменьшается один раз для каждой пары, поэтому объём работы составляет O(V + E).

Почему оставшийся курс означает наличие цикла: если очередь опустела, а курс a не пройден, его счётчик больше 0, значит, одна из его обязательных дисциплин, b, тоже не была пройдена. То же верно для b и так далее. Переход от курса к непройденной обязательной дисциплине никогда не останавливается, поэтому он возвращается к уже посещённому курсу, образуя цикл. Во втором примере ни один счётчик изначально не равен 0, очередь изначально пуста, и ни один из трёх курсов не пройден.

Верно и обратное: курс в цикле зависит от другого курса из того же цикла, поэтому его счётчик не может стать равным 0, пока не пройден тот курс, и ни один из них не будет пройден первым. Значит, утверждения «пройдены все курсы» и «циклов нет» равнозначны. В качестве бонуса: порядок, в котором курсы извлекаются из очереди, задаёт допустимое расписание.

Алгоритм

Для каждой пары [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, а не только те, что встречаются в паре.
Курс является собственной предпосылкой: [2, 2]. Это цикл длины один: входящая степень курса никогда не станет равной 0, и ответ — false.
Два состояния вместо трёх при поиске в глубину. В ромбе 0 → 1, 0 → 2, 1 → 3, 2 → 3 курс 3 достигается дважды, что выглядит как цикл, если отслеживать только «посещённые» узлы. Петлю образует только стрелка, ведущая обратно в текущий путь.
Рекурсия в длинных цепочках. Цепочка из 5 000 курсов приводит к 5 000 уровням вызовов — это превышает стандартный лимит Python в 1 000.
Возврат true при опустошении очереди без сравнения количества пройденных курсов с numCourses.

Частые вопросы4

Какова временная сложность задачи Course Schedule?

O(V + E), где V — количество курсов, а E — количество пар, при использовании алгоритма Кана или поиска в глубину. При построении списков каждая пара считывается один раз, каждый курс попадает в очередь не более одного раза, а каждая пара один раз уменьшает один счетчик. Для списков и счетчиков требуется O(V + E) памяти.

Почему оставшийся курс в алгоритме Кана означает, что в графе есть цикл?

Курс остаётся только в том случае, если его счётчик так и не достиг 0, а значит, остаётся и хотя бы один из его обязательных предварительных курсов. Проследи за этим ожиданием от курса к курсу: каждый шаг ведёт к другому оставшемуся курсу, и поскольку число курсов конечно, в какой-то момент путь должен вернуться к уже посещённому курсу. Участок между двумя посещениями образует цикл.

Что использовать для расписания курсов: BFS или DFS?

Оба алгоритма работают за O(V + E). Алгоритм Кана, вариант с поиском в ширину, не требует беспокоиться о глубине рекурсии и сразу выдаёт допустимый порядок курсов. Поиск в глубину с тремя состояниями работает так же быстро и является естественным выбором, когда нужно также сообщить о цикле, поскольку его образуют курсы в стеке.

Что такое топологическая сортировка?

Порядок узлов ориентированного графа, при котором каждая стрелка направлена вперёд; здесь — порядок курсов, в котором каждый курс, являющийся предварительным условием, стоит раньше курса, которому он необходим. Такой порядок существует тогда и только тогда, когда в графе нет циклов, и порядок, в котором алгоритм Кана выбирает курсы, — один из таких порядков. Задача Course Schedule спрашивает, существует ли топологический порядок.

Python

def canFinish(numCourses, prerequisites):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

numCourses = 4
prerequisites = [[1, 0], [2, 1], [3, 1]]

Ожидается

true

Course Schedule

Функция

Ограничения

Примеры

Подсказки

Решение

Проходи каждый бесплатный курс, раунд за раундом

Поиск в глубину с тремя состояниями

Алгоритм Кана

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи