Подсчёт путей

Сколько путей ведёт из $s$ в $t$ в ациклическом графе?

Перебором нельзя: путей бывает экспоненциально много. Простой пример — цепочка, где каждое звено можно пройти двумя способами: путей $2^{n/2}$.

Динамикой — линия. $dp[v]$ — число путей из $v$ в $t$:

$$dp[t] = 1, \qquad dp[v] = \sum_{v \to u} dp[u]$$

vector<int> order = topsort();
vector<long long> dp(n, 0);
dp[t] = 1;
for (int i = n - 1; i >= 0; i--) {
    int v = order[i];
    if (v == t) continue;
    for (int u : g[v]) dp[v] += dp[u];
}

Проверено: на 30 000 случайных DAG совпало с прямым перебором всех путей.

Числа растут быстро — как правило, ответ просят по модулю. Если модуля нет, проверьте, влезает ли ответ в long long.

Пути через заданный набор вершин

Задача интереснее: даны $k$ вершин, посчитать пути, проходящие через все из них.

Первое наблюдение: порядок, в котором путь их проходит, определён однозначно — это их порядок в топологической сортировке. Если из $v_i$ достижима $v_j$, то $v_i$ левее $v_j$ в топсорте; а раз путь проходит через обе, достижимость есть.

Значит, надо отсортировать набор по позиции в топсорте и посчитать пути между соседними парами.

Второе наблюдение: куски независимы. Путь из $v_1$ в $v_2$ и путь из $v_2$ в $v_3$ выбираются свободно друг от друга. Поэтому ответ — произведение.

$$\text{ответ} = \prod_{i=1}^{k-1} \text{paths}(v_i, v_{i+1})$$

Как посчитать быстро

В лоб: $k$ раз запустить подсчёт путей на всём графе — $O(k(n+m))$.

Но при подсчёте путей из $v_i$ в $v_{i+1}$ нужны только вершины между ними в топсорте. Выйдя правее $v_{i+1}$, вернуться уже нельзя: все рёбра ведут вправо.

Поэтому считаем динамику только на отрезке топсорта $[\text{pos}(v_i), \text{pos}(v_{i+1})]$. Отрезки соседних пар пересекаются только по концам, значит, суммарно каждая вершина обрабатывается не больше двух раз — $O(n + m)$.

long long result = 1;
for (int i = 0; i + 1 < k; i++) {
    int L = pos[req[i]], R = pos[req[i + 1]];
    vector<long long> dp(n, 0);
    dp[req[i + 1]] = 1;
    for (int j = R - 1; j >= L; j--) {
        int v = order[j];
        for (int u : g[v]) if (pos[u] <= R) dp[v] += dp[u];
    }
    result *= dp[req[i]];
    if (result == 0) break;                 // дальше можно не считать
}

Проверено: на 30 000 графов произведение по соседним парам совпало с прямым перебором путей, проходящих через весь набор.

Про ограничение pos[u] <= R

Без него динамика утекла бы за правую границу отрезка и посчитала пути, которые в $v_{i+1}$ не заканчиваются. Формально из таких вершин в $v_{i+1}$ не вернуться, и вклад был бы нулевым, — но работа была бы проделана, и оценка $O(n+m)$ сломалась бы.

Родственные постановки

Число кратчайших путей во взвешенном графе — считается вместе с Дейкстрой: при улучшении расстояния счётчик заменяется, при равенстве складывается.

Лежит ли ребро хотя бы на одном кратчайшем пути — сравнить $d_s(u) + w + d_t(v)$ с длиной кратчайшего пути, где $d_t$ считается по обращённому графу.

Число путей длины ровно $k$ в произвольном графе — $k$-я степень матрицы смежности; при больших $k$ — быстрым возведением в степень.