DSA Interview Prep · Урок

Расписание курсов I и II

«Расписание курсов I и II» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Обзор задачи

Расписание курсов I (LeetCode 207): даны n курсов и список пар prerequisites [a, b], где «b нужно пройти до a»; определите, можно ли пройти все курсы. Расписание курсов II (LeetCode 210): верните фактический порядок прохождения курсов или пустой массив, если это невозможно. Обе задачи сводятся к топологической сортировке ориентированного графа, в котором предварительные требования представлены рёбрами.

Моделирование графа

Постройте ориентированный граф: для каждой пары предварительных требований [a, b] добавьте ребро b → a («b должно идти перед a» означает, что b ведёт к a). Вычислите входящие степени для каждого курса. Курс с нулевой входящей степенью не имеет предварительных требований, поэтому его можно пройти сразу. Задача разрешима тогда и только тогда, когда в этом графе нет цикла, то есть круговой зависимости.

from collections import defaultdict

def build_graph(n, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * n
    for a, b in prerequisites:  # b must come before a
        graph[b].append(a)
        in_degree[a] += 1
    return graph, in_degree

graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind)   # [0, 1, 1, 2]
print('Graph edges:', dict(graph))

Расписание курсов I: решение алгоритмом Кана

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

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    
    while queue:
        course = queue.popleft()
        count += 1
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))        # True
print(canFinish(2, [[1,0],[0,1]])) # False

Расписание курсов II: возврат порядка

Решение такое же, как для «Расписания курсов I», но по мере обработки собирайте порядок курсов. Верните этот порядок, если в нём присутствуют все курсы; в противном случае верните пустой список.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    
    while queue:
        course = queue.popleft()
        order.append(course)
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Расписание курсов с DFS

Альтернативный подход использует обнаружение циклов с помощью DFS. У курсов есть три состояния: не посещён (0), обрабатывается (1), обработан (2). Если во время DFS мы снова достигаем курса, который уже обрабатывается, значит, существует цикл. Функционально этот подход эквивалентен алгоритму Кана, но использует рекурсивный DFS.

from collections import defaultdict

def canFinish_dfs(numCourses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)
    
    # 0=unvisited, 1=in-progress, 2=done
    state = [0] * numCourses
    
    def has_cycle(course):
        if state[course] == 1: return True  # back edge
        if state[course] == 2: return False # already cleared
        state[course] = 1
        for nxt in graph[course]:
            if has_cycle(nxt):
                return True
        state[course] = 2
        return False
    
    return not any(has_cycle(i) for i in range(numCourses))

print(canFinish_dfs(2, [[1,0]]))        # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # False

Почему направление рёбер важно

Распространённая ошибка — перепутать направление ребра: если предварительное требование задано как [a, b] и означает «b раньше a», добавьте ребро b → a, а не a → b. Направление ребра должно отражать поток зависимостей: стрелка идёт от того, что нужно выполнить первым, к тому, что от этого зависит. При неправильном направлении обнаружение циклов и порядок будут обращены, что приведёт к неверным результатам в задачах с несколькими зависимостями.

Расписание курсов III: жадный вариант

Расписание курсов III (LeetCode 630) — это другая задача: у курсов есть длительность и сроки, а требуется максимизировать число пройденных курсов. Она решается жадным методом с максимальной кучей: всегда сначала выбирайте курс с самым поздним сроком; если добавление курса нарушает его срок, замените его самым длительным из уже выбранных курсов (если тот курс длиннее). Это жадная задача, а не задача на топологическую сортировку, что показывает важность внимательного чтения условия.

Обработка изолированных вершин

Курсы без предварительных требований и зависимых от них курсов — это изолированные вершины: у них нулевая входящая степень и нет исходящих рёбер. Алгоритм Кана корректно обрабатывает их: они сразу добавляются в очередь и обрабатываются. Обязательно инициализируйте входящие степени для ВСЕХ вершин от 0 до n-1, включая те, которые не встречаются в списке предварительных требований, иначе они будут пропущены.

# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict

def findOrder_isolated(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses  # initialise ALL nodes
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        c = queue.popleft(); order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    return order if len(order) == numCourses else []

print(findOrder_isolated(4, [[1,0]]))  # [0,1,2,3] or [2,3,0,1] etc.

Время параллельного прохождения курсов

Параллельные курсы II: найдите минимальное число семестров, необходимое для прохождения всех курсов, если за семестр разрешено проходить не более k курсов и нужно соблюдать предварительные требования. Для этого нужна послойная обработка алгоритмом Кана с использованием DP на битовых масках для ограничения выбора k курсов — значительно более сложная задача, объединяющая топологическую сортировку и DP на битовых масках.

Стратегия общения на собеседовании

Если на собеседовании Вам встретилась задача типа «Расписание курсов»: (1) сразу определите её как задачу на топологическую сортировку и обнаружение циклов; (2) смоделируйте граф, уточнив направление рёбер; (3) выберите алгоритм Кана (BFS) для простоты или DFS, если Вы лучше с ним знакомы; (4) явно обработайте случай цикла; (5) назовите временную сложность O(V+E). Такой структурированный подход демонстрирует системные навыки решения задач.

Комплексная проверка

Проверьте оба решения на разных входных данных, чтобы убедиться в их корректности. Подход Кана спокойно обрабатывает несколько допустимых порядков: в качестве ответа для «Расписания курсов II» подходит любой допустимый топологический порядок.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        c = queue.popleft(); order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    return order if len(order) == numCourses else []

print(findOrder(1, []))                    # [0]
print(findOrder(2, [[0,1]]))              # [1, 0]
print(findOrder(3, [[1,0],[2,1]]))        # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]]))        # [] cycle

Быстрая проверка

Проверьте своё понимание концепций «Структуры данных & алгоритмы — подготовка к собеседованию по программированию» из этого урока.

Итоги урока

В этом уроке Вы узнали, что «Расписание курсов I» и «Расписание курсов II» используют топологическую сортировку с ребром b → a для предварительного требования [a, b], «Расписание курсов I» лишь проверяет, что порядок содержит n курсов, а «Расписание курсов II» возвращает сам порядок, а обнаружение циклов с помощью DFS и трёх состояний является допустимой альтернативой подходу Кана на основе BFS. Далее мы изучим алгоритм Kosaraju для сильно связных компонент.

Часто задаваемые вопросы

Урок «Расписание курсов I и II» бесплатный?

Да — полный текст урока «Расписание курсов I и II» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Расписание курсов I и II»?

Представьте обязательные предварительные курсы в виде ориентированного графа и используйте топологическую сортировку, чтобы определить, можно ли пройти все курсы и в каком порядке Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Расписание курсов I и II»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к DSA Interview Prep