Задача 3 — Можно ли закрыть все курсы

Есть N курсов и M пар зависимостей (i, j): «перед курсом j надо сдать курс i». Определи, можно ли закрыть все курсы.

Перевод на человеческий язык. Каждая зависимость (i, j) — это стрелка i → j, «сначала i, потом j». Вопрос «можно ли закрыть все курсы?» = «можно ли выстроить курсы в очередь так, чтобы каждый шёл после своих предусловий?». Это возможно тогда и только тогда, когда нет замкнутого круга зависимостей (цикла).

Определения с иллюстрацией

Когда МОЖНО: граф без цикла (DAG)

0 1 2 3

Зависимости: 0→1, 0→2, 1→3, 2→3

Возможный порядок сдачи: 0 → 1 → 2 → 3

Стрелки всегда идут «вперёд» по этому порядку. Ни один курс не ждёт сам себя.

Когда НЕЛЬЗЯ: есть цикл

0 1 2

Зависимости: 0→1, 1→2, 2→0

тупик чтобы начать 0, нужен 2; для 2 нужен 1; для 1 нужен 0…

Круг зависимостей — ни один курс нельзя начать первым. Закрыть всё невозможно.

Алгоритм Кана — «как студент проходит курсы»

Ключевая величина — «входящая степень» indeg[v]: сколько ещё несданных предусловий у курса v (сколько стрелок в него входит).

Интуиция. Курс с indeg = 0 — это курс без предусловий, его можно взять прямо сейчас. Когда ты «сдаёшь» курс, ты убираешь его стрелки → у зависящих курсов indeg уменьшается. Кто обнулился — теперь тоже доступен.

Шаги

Прогон на DAG 0→1, 0→2, 1→3, 2→3

шагочередь (indeg=0)сдаёмчто меняетсяprocessed
старт[0]—indeg: 1→1, 2→1, 3→20
1[1, 2]0indeg[1]→0, indeg[2]→01
2[2, 3?]1indeg[3]→12
3[3]2indeg[3]→03
4[ ]3—4
processed = 4 = N → можно закрыть все курсы. ✓

Прогон на цикле 0→1, 1→2, 2→0

У всех трёх вершин indeg = 1 (в каждую входит стрелка). Очередь стартует пустой — ни одного курса с indeg 0. Цикл сразу завершается.

processed = 0 ≠ 3 → закрыть нельзя. ✗ Никто не смог стать «доступным» — это и есть признак цикла.

Код (Python)

from collections import deque


def can_finish(n, deps):
    # deps: список пар (i, j) — "сначала i, потом j"
    g = [[] for _ in range(n)]   # список смежности
    indeg = [0] * n                  # число несданных предусловий

    for i, j in deps:
        g[i].append(j)
        indeg[j] += 1

    # все курсы без предусловий — доступны сразу
    dq = deque(v for v in range(n) if indeg[v] == 0)

    processed = 0
    while dq:
        v = dq.popleft()
        processed += 1          # "сдали" курс v
        for u in g[v]:
            indeg[u] -= 1       # у зависящего стало на 1 предусловие меньше
            if indeg[u] == 0:    # все предусловия сданы → доступен
                dq.append(u)

    return processed == n     # сдали все? значит цикла нет

Время O(N + M)   Память O(N + M)
Один проход по рёбрам для indeg, потом каждая вершина и каждое ребро обрабатываются ровно один раз.

Подводные камни

Мини-проверка себя