Задача 7 — Число путей в DAG

Дан ориентированный граф без циклов (DAG). Найти число различных путей от s до t.

Перевод на человеческий язык. Представь развилки дорог, где все стрелки односторонние и назад не вернуться (нет циклов). Сколькими разными маршрутами можно доехать из города s в город t? Считать по одному — безнадёжно (их могут быть миллионы). Идея: число маршрутов из вершины = сумма маршрутов из всех вершин, куда из неё ведёт стрелка.

Идея: динамика по вершинам

dp[v] = число путей из вершины v в t.

База: dp[t] = 1 (из t в t ровно один путь — пустой, «стоять на месте»).
Переход: dp[v] = Σ dp[u] по всем рёбрам (v → u). Каждый сосед u добавляет столько путей, сколько их ведёт из него в t.
Ответ: dp[s].

Рёбра: 0→1, 0→2, 1→2, 1→3, 2→3; s=0, t=3

Считаем dp «от t назад»:

dp[3]=1 (база)
dp[2]=dp[3]=1
dp[1]=dp[2]+dp[3]=1+1=2
dp[0]=dp[1]+dp[2]=2+1=3

3 пути: 0→1→3, 0→1→2→3, 0→2→3.

Почему нужен топологический порядок

Чтобы посчитать dp[v], нужно уже знать dp всех его соседей u (куда ведут стрелки из v). Значит соседи должны быть обработаны раньше v.

Это ровно обратный топологический порядок. На практике два удобных способа:

Топосорт + идём в прямом порядке от s «вперёд» (вариант ниже в коде): dp[s]=1, и проталкиваем dp[v] соседям dp[u] += dp[v]. Тогда к моменту обработки v все пути, ведущие в v, уже учтены.
Рекурсия с мемоизацией «от s назад» (как в указании семинара): dp[v] = Σ dp[u], считаем лениво, кэшируем.

Почему это не работает на графе с циклом: по циклу можно крутиться сколько угодно → путей бесконечно, dp не определён. Поэтому условие задачи — именно DAG.

Прогон (вариант «вперёд от s»)

dp[s]=1, остальные 0. Идём в топопорядке 0,1,2,3 и проталкиваем: для ребра (v→u) делаем dp[u] += dp[v].

обрабатываем v	dp[v]	проталкиваем	dp после
старт	—	—	[1, 0, 0, 0]
0	1	dp[1]+=1, dp[2]+=1	[1, 1, 1, 0]
1	1	dp[2]+=1, dp[3]+=1	[1, 1, 2, 1]
2	2	dp[3]+=2	[1, 1, 2, 3]
3	3	— (это t)	[1, 1, 2, 3]

dp[t] = dp[3] = 3. Совпадает с подсчётом «от t назад». ✓

Код (Python)

from collections import deque


def count_paths_dag(n, edges, s, t):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1

    # топологический порядок (Кан)
    order = []
    dq = deque(v for v in range(n) if indeg[v] == 0)
    while dq:
        v = dq.popleft()
        order.append(v)
        for u in g[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                dq.append(u)

    # dp: число путей из s в каждую вершину
    dp = [0] * n
    dp[s] = 1
    for v in order:
        if dp[v]:                 # из недостижимых проталкивать нечего
            for u in g[v]:
                dp[u] += dp[v]   # каждый путь до v продолжается в u

    return dp[t]

Время O(|V| + |E|) Память O(|V| + |E|)
Топосорт — O(V+E), затем каждое ребро обрабатывается ровно один раз в dp.

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

Только DAG. При наличии цикла путей бесконечно — задача определена лишь на ацикличном графе. Если не гарантировано — сначала проверь ацикличность (та же задача 3).
Числа растут экспоненциально. Путей может быть astрономически много. В Python int безразмерный — переполнения нет. Но если в условии просят ответ по модулю (часто 10⁹+7), считай dp[u] = (dp[u] + dp[v]) % MOD.
Направление dp. Здесь «вперёд от s»: dp[s]=1, проталкиваем соседям. В семинаре — «от t назад»: dp[v]=Σdp[u]. Оба верны, не смешивай в одной реализации.
t недостижим из s. Тогда dp[t] останется 0 — корректный ответ «путей нет».
Кратные рёбра. Если между v и u два ребра — это два разных пути, и dp учтёт оба (мы не дедуплицируем соседей). Обычно так и надо.

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

☐ dp[t]=1 (база), dp[v]=Σ dp[соседей) — понимаю смысл.
☐ Нужен топопорядок: сосед обрабатывается раньше / dp проталкивается вперёд.
☐ Только DAG; на цикле путей бесконечно.
☐ Большие числа → при необходимости считать по модулю.
☐ Асимптотика O(V+E).