Динамика на ациклическом графе

В дереве порядок пересчёта задавал обход. В произвольном графе порядка нет вовсе: состояния могут зависеть друг от друга по кругу.

В ориентированном ациклическом графе (DAG) порядок есть — это топологическая сортировка. Все рёбра идут слева направо, значит, зависимости упорядочены.

Пример: самый длинный путь

В произвольном графе задача о самом длинном простом пути NP-полна: умей мы её решать, умели бы проверять существование гамильтонова пути. В DAG она решается за линию.

$dp[v]$ — длина самого длинного пути, начинающегося в $v$. Перебираем первое ребро:

$$dp[v] = \max_{v \to u} \bigl(dp[u] + 1\bigr)$$

vector<int> order = topsort();
vector<long long> dp(n, 0);
for (int i = n - 1; i >= 0; i--) {          // справа налево по топсорту
    int v = order[i];
    for (int u : g[v]) dp[v] = max(dp[v], dp[u] + 1);
}

Идём справа налево: когда доходим до $v$, все вершины, куда из неё ведут рёбра, уже посчитаны — они правее.

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

Вперёд и назад

Одну и ту же динамику можно писать двумя способами, и путаница в терминах здесь обычная.

Назад — вычисляем своё состояние, читая чужие: dp[v] = max(dp[v], dp[u] + 1). Идём в том порядке, где нужные состояния уже готовы.

Вперёд — своим состоянием обновляем чужие: dp[u] = max(dp[u], dp[v] + 1). Идём так, чтобы к моменту прихода в вершину её больше никто не обновит.

for (int i = 0; i < n; i++) {               // слева направо
    int v = order[i];
    for (int u : g[v]) dp[u] = max(dp[u], dp[v] + 1);
}

Здесь dp[v] — длина пути, кончающегося в $v$. Обе версии верны, обе линейны; выбор — вопрос удобства в конкретной задаче.

Признак, по которому их различают: смотрите на левую часть присваивания. Меняем своё — назад. Меняем чужое — вперёд.

Без топсорта

Порядок можно не строить явно. Обход в глубину сам обеспечивает нужный: к моменту выхода из вершины все достижимые из неё посчитаны.

void dfs(int v) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) dfs(u);
        dp[v] = max(dp[v], dp[u] + 1);      // здесь dp[u] уже готово
    }
}

Это ровно тот же топсорт, просто не выписанный в массив: обход считает порядок по временам выхода, и мы пользуемся им на месте.

Так пишется только динамика назад: вперёд не выйдет, потому что момент, когда вершину больше никто не обновит, при таком обходе неизвестен.

Взвешенный вариант

Меняется +1 на +вес ребра, и всё. В отличие от Дейкстры, знак веса роли не играет: ацикличность уже гарантирует, что бесконечно улучшаться некуда.

Поэтому кратчайшие и длиннейшие пути в DAG считаются одинаково — заменой max на min. В общем графе такой симметрии нет: кратчайшие пути ищутся, длиннейшие нет.

Что ещё считается так же

Число путей — заменить max на сумму; про это отдельно.

Достижимость — заменить на «или».

Длина кратчайшего пути — заменить на min.

Число путей максимальной длины — считать пару (длина, количество) и складывать количества при равенстве длин.

Общее правило: если задача про пути в DAG и ответ собирается из ответов для соседей — это динамика по топологическому порядку.