Как посчитать число различных путей в DAG из истока в сток (счётное ДП на ациклическом графе)?
Дан ориентированный ациклический граф (DAG) на $n \le 10^5$ вершинах. Нужно число различных путей из вершины-истока $s$ в сток $t$ (число может быть огромным — ответ по модулю $10^9+7$). Как свести к ДП и почему ациклчиность тут критична?
2 ответа
Число путей в DAG — счётное ДП по топологическому порядку. ways[v] = число путей из истока s в вершину v. База ways[s] = 1, переход — каждое ребро u → v добавляет к ways[v] все пути, дошедшие до u:
$$ways[v] = \sum_{(u \to v)} ways[u]$$
Чтобы при вычислении ways[v] все ways[u] предшественников были готовы, идём в топологическом порядке:
const long long MOD = 1e9 + 7;
int n, s, t;
vector<vector<int>> g; // список смежности
vector<int> order; // топосортировка (Kahn или DFS)
vector<long long> ways(n, 0);
ways[s] = 1;
for (int u : order) // в топопорядке
for (int v : g[u])
ways[v] = (ways[v] + ways[u]) % MOD; // суммируем по модулю
// ответ ways[t]
Почему ациклчиность критична: если бы был цикл, число путей было бы бесконечным (можно крутиться по циклу), и топосортировки не существовало бы — ДП не определено. В DAG же зависимости подзадач сами образуют DAG, и топопорядок гарантирует корректность.
Сложность $O(n + m)$ времени и памяти. Остаток по модулю берём на каждом сложении — числа путей растут экспоненциально.
Альтернатива явной топосортировке — рекурсия с мемоизацией «сверху»: count(v) = число путей из v в сток t, count(t)=1, count(v)=sum count(u) по рёбрам v→u. Это естественно обходит граф зависимостей в нужном порядке без отдельной топосортировки:
long long count_paths(int v) {
if (v == t) return 1;
if (vis[v]) return memo[v];
vis[v] = true;
long long res = 0;
for (int u : g[v]) res = (res + count_paths(u)) % MOD;
return memo[v] = res;
}
Грабля — глубина рекурсии до $10^5$ (Stack Overflow на длинном DAG); для надёжности на проде лучше итеративная топосортировка Kahn. И не забудь модуль: без него long long переполнится уже на десятках развилок.