Тема занятия — графы, и расшифровывается она как DFS (обход в глубину). Все графы на этом занятии удобно считать ориентированными: именно для ориентированных графов вводятся времена входа-выхода, топсорт и компоненты сильной связности.
Формально граф — это пара $G = (V, E)$, где $V$ — множество вершин, а $E \subseteq V \times V$ — множество рёбер. Для ориентированного графа ребро — упорядоченная пара $(u, v)$ («из $u$ в $v$»); для неориентированного — неупорядоченная $\{u, v\}$.
| Способ | Как устроен | Память | Проверка ребра $u\to v$ | Перебор соседей $u$ |
|---|---|---|---|---|
| Список смежности | vector<vector<int>> g; g[u] хранит всех соседей $u$ | $O(V+E)$ | $O(\deg u)$ | $O(\deg u)$ |
| Матрица смежности | bool a[V][V] | $O(V^2)$ | $O(1)$ | $O(V)$ |
| Список рёбер | vector<pair<int,int>> edges | $O(E)$ | $O(E)$ | $O(E)$ |
Почти все алгоритмы занятия работают со списком смежности: он даёт суммарный обход всех соседей за $O(V+E)$, что и определяет время работы DFS.
vector<vector<int>> g; // g[v] — список исходящих рёбер
void add_edge(int u, int v) { // ориентированное ребро u -> v
g[u].push_back(v);
}
// для неориентированного графа добавляем оба направления:
void add_undirected(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
// взвешенные рёбра: храним пары (сосед, вес)
vector<vector<pair<int,int>>> gw;Индексация. Если вершины нумеруются с $0$ (как в массивах C++), размер — $n$. Если входные данные нумеруют вершины с $1$, удобно держать размер $n+1$ и не трогать индекс $0$; либо сразу вычитать единицу при чтении. Главное — не смешивать соглашения.
Степени. Для ориентированного графа различают исходящую степень $\deg^+ v = |g[v]|$ и входящую $\deg^- v$. Сумма всех исходящих степеней равна числу рёбер: $\sum_v \deg^+ v = E$. В неориентированном графе сумма степеней чётна и равна $2E$ (лемма о рукопожатиях).
Классический DFS принимает вершину, помечает её использованной и рекурсивно запускается от всех ещё не посещённых соседей. В main мы перебираем все вершины и запускаем DFS от каждой непосещённой — так обходятся все компоненты слабой связности.
vector<vector<int>> g;
vector<char> used;
void dfs(int v) {
used[v] = true;
for (int u : g[v])
if (!used[u]) dfs(u);
}
int main() {
// ... ввод графа ...
int n = g.size();
used.assign(n, false);
for (int v = 0; v < n; ++v)
if (!used[v]) dfs(v);
}Теперь введём времена входа-выхода. Заведём глобальный счётчик времени timer, изначально равный нулю, и два вектора tin, tout. Каждый раз, когда мы входим в DFS от вершины, записываем текущее время в tin[v] и увеличиваем счётчик; каждый раз, когда выходим из DFS, записываем время в tout[v] и снова увеличиваем счётчик.
vector<int> tin, tout;
int timer = 0;
void dfs(int v) {
used[v] = true;
tin[v] = timer++; // вошли в v
for (int u : g[v])
if (!used[u]) dfs(u);
tout[v] = timer++; // вышли из v
}timer++tin[v] = timer++ сначала записывает в tin[v] старое значение, а лишь потом увеличивает счётчик. Поэтому событие «вход в $v$» и событие «выход из $v$» получают разные номера, а максимальное значение счётчика — около $2n-1$ (каждая вершина входит и выходит ровно один раз).
Каждой вершине соответствует отрезок $[\mathrm{tin}[v], \mathrm{tout}[v]]$: точка входа и точка выхода. Именно эти числа мы дальше используем для топсорта, поиска предков и компонент сильной связности.
Почему так. Исполнение рекурсии структурно: вызов функции не может «прыгать» внутрь уже начатого вызова чужой функции — вложенные вызовы образуют стек. Вход в $v$ и выход из $v$ — это моменты старта и завершения одного вызова. Поэтому, если $v$ начался внутри вызова $u$ (то есть $\mathrm{tin}[u] < \mathrm{tin}[v] < \mathrm{tout}[u]$), то вызов $u$ не мог завершиться раньше $v$, значит $\mathrm{tout}[v] < \mathrm{tout}[u]$ — отрезок $v$ вложен в отрезок $u$. Иначе вызов $v$ произошёл до или после вызова $u$, и отрезки не пересекаются. Это частный случай «структурности» вызовов; из-за такой предсказуемости, кстати, в современном программировании не используют goto для «прыжков в середину» чужого кода.
Топологическая сортировка ориентированного графа — это такое упорядочивание всех вершин $v_1, v_2, \dots, v_n$, что вдоль него все рёбра идут строго слева направо.
Топсорт, вообще говоря, не единственный: например, у графа из двух вершин без рёбер корректны оба порядка $1,2$ и $2,1$. Пока нас интересует «хоть какая-нибудь» корректная сортировка.
Если цикл есть, топсорта нет. Предположим противное: пусть корректный топсорт есть. Посмотрим на вершины цикла в этом порядке. Идя по циклу, мы на одном из его рёбер обязаны вернуться «назад» — то есть пройти по ребру справа налево. Но в топсорте таких рёбер быть не должно. Противоречие. Значит, при наличии цикла построить топсорт невозможно.
Если цикла нет, топсорт есть. Это мы сейчас и научимся делать конструктивно. Классическая идея — запустить DFS и выписывать вершины по ходу обхода, однако мы «изобретём» алгоритм с нуля, опираясь на времена выхода.
Рассмотрим ребро $u \to v$, про которое известно, что из $v$ нельзя добраться обратно в $u$ (в частности, в ациклическом графе это выполнено всегда). Что можно сказать про времена входа и выхода?
Доказательство. Возможны два случая. Если DFS запустился сначала от $v$, то он целиком завершится (выйдет из $v$) до того, как мы вообще начнём вызов от $u$, — тогда $\mathrm{tout}[v] < \mathrm{tout}[u]$. Иначе DFS запустился раньше от $u$; тогда в ходе вызова $u$ мы обязаны рано или поздно дойти до $v$ (по ребру $u\to v$) и запустить рекурсивный вызов от $v$ (если только не посетили $v$ ещё раньше — тогда тем более вышли из него). В любом случае вызов $v$ завершится внутри вызова $u$, значит $\mathrm{tout}[v] < \mathrm{tout}[u]$. Лемма доказана.
На самом деле верно и более сильное утверждение: если есть путь $u \leadsto v$ и нет пути $v \leadsto u$, то $\mathrm{tout}[v] < \mathrm{tout}[u]$ — всё по той же логике вложенных вызовов.
Обобщим локальное условие на глобальный порядок: выпишем вершины в порядке убывания $\mathrm{tout}$. Покажем, что это корректный топсорт.
Корректность. Пусть порядок — $v_1, \dots, v_n$ с $\mathrm{tout}[v_1] > \mathrm{tout}[v_2] > \dots > \mathrm{tout}[v_n]$. Предположим противное: есть ребро, идущее «справа налево», то есть $v_i \to v_j$ при $i > j$. По лемме (обратного пути нет, иначе был бы цикл) имеем $\mathrm{tout}[v_j] < \mathrm{tout}[v_i]$. Но из $i > j$ следует $\mathrm{tout}[v_i] < \mathrm{tout}[v_j]$. Противоречие. Значит, рёбер справа налево нет — порядок корректный.
tout, а не за tinНаивно можно запустить DFS, собрать пары $(\mathrm{tout}, v)$ и отсортировать их — это $O((V+E) + V\log V)$. Есть два улучшения.
Сортировка подсчётом. Значения $\mathrm{tout}$ лежат в диапазоне $[0, 2n-1]$ (каждая вершина входит и выходит один раз). Значит, подходит сортировка подсчётом за $O(V)$; суммарно — $O(V+E)$.
Ещё проще — писать вершину при выходе. Заметим: когда timer увеличивается в конце DFS, мы сразу же записываем эту вершину в массив. Поэтому, если в конце каждого DFS делать push_back(v), массив окажется записанным в порядке возрастания $\mathrm{tout}$. Остаётся его перевернуть.
vector<int> order;
void dfs(int v) {
used[v] = true;
for (int u : g[v])
if (!used[u]) dfs(u);
order.push_back(v); // порядок возрастания tout
}
int main() {
// ... ввод ...
for (int v = 0; v < n; ++v)
if (!used[v]) dfs(v);
reverse(order.begin(), order.end()); // порядок убывания tout = топсорт
}В неориентированном графе компонента связности — это максимальное множество вершин, между любой парой которых есть путь. Отношение «есть путь между $u$ и $v$» — это отношение эквивалентности, а компоненты — его классы эквивалентности.
Найти их просто: запускаем DFS и красим вершины одного запуска в один цвет; каждый новый запуск из main — новый цвет.
int col = 0;
vector<int> color;
void dfs_undirected(int v, int c) {
color[v] = c;
for (int u : g[v])
if (color[u] == -1) dfs_undirected(u, c);
}
// for (int v = 0; v < n; ++v) if (color[v] == -1) dfs_undirected(v, col++);В ориентированном графе пути несимметричны: из $u$ может быть путь в $v$, а обратного пути нет. Поэтому понятие связности разветвляется.
В DAG нетривиальных КСС нет: у любой пары вершин одной КСС из сильной связности следует цикл, что невозможно. Значит, каждая КСС состоит из одной вершины.
Конденсация — это процесс: каждую КСС «сжимаем» в одну вершину, а затем возвращаем рёбра между разными компонентами (между сжатыми вершинами). Полученный граф называют метаграфом, а в разговорной речи — тоже конденсацией.
Кратные рёбра в конденсации неудобны, поэтому обычно для каждой пары компонент оставляют одно ребро (списки смежности сортируют и удаляют дубликаты или хранят как set).
Нам неизвестно, как выделить КСС напрямую, но мы знаем: конденсация — DAG, а на DAG можно строить топсорт. Однако исходный граф циклический, и корректного топсорта у него нет. Зато есть времена выхода.
Почему. Рассмотрим ребро $x_0 \to y_0$ между компонентами ($x_0 \in U$, $y_0 \in V$). Если DFS дошёл до всей компоненты $V$ раньше, чем закрылась некоторая вершина $U$, то сначала обходится вся $V$ (все её вершины выходят), и лишь потом выходит та вершина $U$. Значит, у этой вершины $U$ выход позже, чем у всех вершин $V$. Взяв вершину $U$ с максимальным $\mathrm{tout}$, получаем утверждение.
Отсюда — ключевой вывод: если для каждой компоненты взять максимум $\mathrm{tout}$ по её вершинам, эти максимумы ведут себя как времена выхода в конденсации. Значит, вершина с глобальным максимумом $\mathrm{tout}$ лежит в первой компоненте топсорта конденсации.
Проблема: мы не знаем состав компонент. Если запустить DFS из найденной вершины по исходному графу, он закрасит и другие компоненты — это неправильно. Решение — развернуть рёбра.
В обратном графе из вершины первой компоненты нет исходящих рёбер в другие компоненты (все такие рёбра смотрели в неё). Поэтому DFS по обратному графу из вершины с максимальным $\mathrm{tout}$ закрасит ровно первую компоненту.
Алгоритм (Косарайю).
Почему корректно. На каждом шаге берём непокрашенную вершину с максимальным $\mathrm{tout}$ среди оставшихся — она принадлежит первой (в топсорте конденсации) из ещё не выделенных компонент. DFS по обратному графу не выходит за её пределы и обходит ровно её (по определению КСС все вершины компоненты взаимно достижимы). Значит, каждый запуск выделяет ровно одну новую компоненту.
Сложность. Два обхода + обращение рёбер: $O(V+E)$.
На занятии разобран граф из девяти вершин со следующими рёбрами:
Внутри компонент: $1\to2\to3\to1$; $8\to7\to9\to6\to8$; $4\to5\to4$. Между компонентами: $4\to3$ и $2\to8$.
Прогон первого DFS (стартуем от вершины 1): обходим $1\to2\to3$ (выходим из 3), из 2 идём в 8, затем $8\to7\to9\to6$, выходим 6, 9, 7, 8, затем 2 и 1. Далее из вершины 4: $4\to5$, выходим 5, 4.
Массив выхода (возрастание $\mathrm{tout}$): $3, 6, 9, 7, 8, 2, 1, 5, 4$. Переворачиваем — порядок убывания: $4, 5, 1, 2, 8, 7, 9, 6, 3$.
Обратный граф и покраска.
Первый этап — обычный DFS, пишущий вершину при выходе. Второй этап — DFS по обратному графу, красящий всё достижимое в один цвет.
int n;
vector<vector<int>> g, gr; // gr — обратный граф
vector<char> used;
vector<int> order, comp;
int col = 0;
void dfs1(int v) {
used[v] = true;
for (int u : g[v])
if (!used[u]) dfs1(u);
order.push_back(v); // возрастание tout
}
void dfs2(int v, int c) {
comp[v] = c;
for (int u : gr[v])
if (comp[u] == -1) dfs2(u, c);
}
void build_scc() {
used.assign(n, false);
order.clear();
for (int v = 0; v < n; ++v)
if (!used[v]) dfs1(v);
reverse(order.begin(), order.end()); // убывание tout
comp.assign(n, -1);
for (int v : order)
if (comp[v] == -1) dfs2(v, col++);
}// построение конденсации
vector<pair<int,int>> edges;
vector<vector<int>> cg(col); // граф компонент
for (auto [u, v] : edges) {
if (comp[u] != comp[v])
cg[comp[u]].push_back(comp[v]);
}
// при необходимости убрать дубликаты в каждом cg[i]long long key = (long long)c_u * n + c_v, сложить все ключи в set/unordered_set, а потом раскодировать: c_u = key / n, c_v = key % n. Это стандартный приём упаковки пар в одно число.
order. 2) Обходить не обратный, а исходный граф. 3) Заходить в уже покрашенные вершины — нельзя, иначе перекрасим соседние компоненты. 4) Переполнение при кодировании пар, если n большое.
Вторую часть лекции ведёт второй преподаватель. Идея: динамики на поддеревьях удобно считать DFS-ом, подвесив дерево за произвольный корень.
Задача. Для каждой вершины $v$ найти длину самого длинного пути из $v$ вниз по поддереву («высоту»).
Идея обхода. В дереве нет циклов, поэтому вместо массива used можно передавать в DFS родителя p и не ходить в него. Порядок пересчёта обеспечивает рекурсия: когда мы выходим из вызова ребёнка, его $dp$ уже посчитана.
vector<vector<int>> g;
vector<int> h;
void dfs(int v, int p) {
h[v] = 0; // база: путь из одной вершины имеет длину 0
for (int u : g[v]) {
if (u == p) continue; // не идём к родителю
dfs(u, v);
h[v] = max(h[v], h[u] + 1);
}
}
// ответ: запустить dfs(root, -1)Ответ для корня лежит в его $h$; для любой другой вершины — в её собственной $h[v]$.
Диаметр дерева — самый длинный путь в нём (по количеству рёбер или вершин — несущественно, с точностью до единицы). Диаметров может быть несколько.
Введём две динамики:
где $x$ и $y$ — два наибольших значения $down[u]$ среди детей $u$ (максимум и второй максимум).
Почему три случая. Диаметр поддерева $v$ либо не проходит через $v$ (тогда он целиком лежит в поддереве какого-то ребёнка и это максимум $d[u]$), либо проходит через $v$; во втором случае он либо уходит вниз в одну сторону (тогда это $\max_u down[u]+1$), либо в две разные стороны через двух детей (тогда это $x+y+2$ — два спуска плюс два ребра до детей). Мы не знаем заранее, какой случай реализуется, поэтому берём максимум по всем трём.
vector<vector<int>> g;
vector<int> down, diam;
void dfs(int v, int p) {
down[v] = 0;
diam[v] = 0;
int best = 0, second = 0; // два максимума (down[u] + 1)
for (int u : g[v]) {
if (u == p) continue;
dfs(u, v);
down[v] = max(down[v], down[u] + 1);
diam[v] = max(diam[v], diam[u]);
int d = down[u] + 1;
if (d > best) { second = best; best = d; }
else if (d > second) { second = d; }
}
diam[v] = max(diam[v], best + second); // = x + y + 2
}
// ответ: diam[root]Замечание об альтернативном решении. Диаметр можно найти и без ДП: двумя обходами BFS/DFS (от произвольной вершины найти самую далёкую, затем от неё снова найти самую далёкую — это и будет диаметр). Это решение проще в реализации, но здесь ДП разбирается специально как тренировка техники «динамика на поддереве».
Задача. В дереве выбрать как можно больше вершин так, чтобы никакие две выбранные не были соединены ребром. На произвольных графах это NP-трудно, но на дереве решается ДП за линейное время.
Подвесим дерево. Введём два состояния для каждой вершины:
Ответ — $\max(dp_0[root], dp_1[root])$.
Почему так. Если $v$ не взята, то на каждого ребёнка ограничений нет — ребёнок можно брать или не брать, поэтому для каждого берём максимум. Если $v$ взята, то ни один ребёнок взят быть не может (иначе появилось бы ребро между двумя выбранными), поэтому каждый ребёнок обязан быть «не взят» (состояние $dp_0$), а саму $v$ добавляем к сумме как $+1$.
vector<vector<int>> g;
vector<array<int,2>> dp; // dp[v][0] — v не взята, dp[v][1] — взята
void dfs(int v, int p) {
dp[v][0] = 0;
dp[v][1] = 1;
for (int u : g[v]) {
if (u == p) continue;
dfs(u, v);
dp[v][0] += max(dp[u][0], dp[u][1]);
dp[v][1] += dp[u][0];
}
}
// ответ: max(dp[root][0], dp[root][1])Задача. В ориентированном ациклическом графе найти самый длинный (по числу рёбер) путь. В произвольном графе это NP-трудно (гамильтонов путь), но на DAG решается просто.
Идея. Построим топсорт. В нём все рёбра идут слева направо. Значит, если считать ДП справа налево, то к моменту обработки $v$ все его «правые» соседи уже посчитаны.
vector<vector<int>> g;
vector<int> order = topsort(g); // порядок топсорта, 0..n-1
vector<int> 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);
}
// ответ: max по всем v (или dp[стартовой вершины])Дальше идёт семинар (ведущий — Артём). Задача 1. Дан корневой дерево на $n$ вершинах. Приходят запросы: «вершина $u$ — предок вершины $v$?». Нужно отвечать за $O(1)$ после $O(n)$ препроцессинга.
Решение. Считаем времена входа-выхода обычным DFS. Тогда:
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}tinЗадача 2. В каждой вершине записано число $a_v$. Приходят запросы $(v, d)$: нужно просуммировать $a_u$ по всем потомкам $u$ вершины $v$, находящимся ровно на расстоянии $d$ от неё (то есть на глубине $\mathrm{depth}[v] + d$). Ответить на все запросы за $O(n + q\log n)$.
Ключевые наблюдения.
// byDepth[D] — вершины глубины D в порядке возрастания tin
// pref[D][i] — префиксные суммы a по byDepth[D]
// массив key[D][i] = tin[byDepth[D][i]] — для бинпоиска
// запрос (v, d):
int D = depth[v] + d;
auto &arr = key[D];
int L = lower_bound(arr.begin(), arr.end(), tin[v]) - arr.begin();
int R = upper_bound(arr.begin(), arr.end(), tout[v]) - arr.begin();
long long ans = pref[D][R] - pref[D][L];Задача 3. Дан неизвестный массив $a_0, \dots, a_{n-1}$ и тройки $(l, r, x)$, означающие, что сумма $a_l + a_{l+1} + \dots + a_{r-1} = x$. Нужно восстановить любой подходящий массив (или определить, что его нет) за $O(n + q)$.
Переход к префиксным суммам. Заведём $P_0 = 0$, $P_{i+1} = a_0 + \dots + a_i$. Тогда условие на отрезке переписывается amazingly просто:
Теперь неизвестны уже не $a_i$, а $P_i$, и каждое условие — это соотношение между двумя числами: $P_r = P_l + x$.
Как это стало графом. Сделаем вершинами индексы префиксных сумм $0, 1, \dots, n$. Условие $P_r - P_l = x$ — это ребро между $l$ и $r$ с весом $x$ в одну сторону и $-x$ в другую:
Алгоритм. Запускаем DFS по каждой ещё не посещённой компоненте, назначая стартовое значение (например, $0$) и распространяя его по рёбрам с их весами. Если встречаем ребро в уже посещённую вершину, проверяем согласованность: должно быть $P_u + w = P_v$. Если нет — условие противоречиво, ответа нет.
vector<vector<pair<int,long long>>> g; // (сосед, вес)
vector<long long> P;
vector<char> vis;
bool ok = true;
void dfs(int v, long long val) {
vis[v] = true;
P[v] = val;
for (auto [u, w] : g[v]) {
if (!vis[u]) dfs(u, val + w);
else if (P[u] != P[v] + w) ok = false; // противоречие
}
}
// стартуем каждую компоненту со значения 0
// после этого a[i] = P[i+1] - P[i]Задача 4. Дан неориентированный граф на $n$ вершинах и $m$ рёбрах (без петель и, как договорились на семинаре, без кратных рёбер). Проверить, есть ли в нём цикл чётной длины, за $O(n+m)$.
Идея «покрасить в два цвета и искать конфликт» обнаруживает нечётный цикл (двудольность), а не чётный, поэтому напрямую не годится. Правильный подход опирается на дерево обхода DFS.
Обратное ребро $v \to u$, где $u$ — предок $v$, вместе с древесным путём $u \leadsto v$ образует цикл длины
Значит:
Склейка двух нечётных циклов. Если два нечётных цикла $C_1$ и $C_2$ имеют хотя бы одно общее ребро, их симметрическая разность (объединение без общих рёбер) имеет длину
Она распадается на циклы, и хотя бы один из них чётный. Поэтому достаточно найти два обратных ребра, чьи древесные пути пересекаются по ребру. Делается это так: обрабатываем обратные рёбра по одному и красим рёбра древесного пути от более глубокого конца вверх до предка; если натыкаемся на уже покрашенное ребро — нашли пересечение двух нечётных циклов, а значит, и чётный цикл.
// DFS-дерево: parent[v], depth[v]
// ребро visited[e] для рёбер дерева
// для каждого обратного ребра (v -> anc):
// if ((depth[v] - depth[anc]) % 2 == 1) -> ответ "ЕСТЬ чётный цикл"
// else идём от v вверх до anc:
// если ребро уже покрашено -> ответ "ЕСТЬ чётный цикл"
// иначе красим его
// если обработали все рёбра без конфликта -> чётного цикла нетЗадача 8 (ведущий — Тимофей). Дан DAG на $n$ вершинах и $k$ выделенных вершин $v_1, \dots, v_k$. Нужно посчитать число путей из $v_1$ в $v_k$, которые проходят через все выделенные вершины (каждую хотя бы раз, порядок внутри — в каком угодно порядке). Две асимптотики: $O\big(k\,(n+m)\big)$ и $O(n+m)$.
Итак, порядок выделенных вершин задаётся их порядком в любом топсорте. Обозначим его $p_1, \dots, p_k$ (должно быть $p_1 = v_1$, $p_k = v_k$).
Первое решение, $O(k(n+m))$. Число путей через все выделенные вершины равно произведению числа путей между соседними выделенными вершинами:
В самом деле, путь распадается на независимые части «от $p_i$ до $p_{i+1}$», и любые комбинации частей склеиваются в корректный путь (промежуточные части не пересекаются, так как между соседними выделенными вершин других выделенных нет, а порядок фиксирован). Каждую часть считаем ДП по топсорту: $dp[v] = \sum_{v\to u} dp[u]$, база $dp[p_{i+1}] = 1$. Итого $O(k(n+m))$.
Второе решение, $O(n+m)$. Построим топсорт один раз. В нём выделенные вершины идут в порядке $p_1, \dots, p_k$. Они делят топсорт на отрезки. Ключевой факт: любой путь из $p_i$ в $p_{i+1}$ не может «выпрыгнуть» за пределы отрезка между ними — все рёбра идут слева направо, и вернуться к $p_{i+1}$ из более правой части невозможно. Поэтому ДП можно считать по всему графу, но для каждой пары «обрезать» рёбра, ведущие правее следующей выделенной вершины. Каждое ребро при этом обрабатывается один раз, так как отрезки не пересекаются: суммарно $O(n+m)$.
// order — топсорт; pos[v] — позиция v в order
// находим p[0..k-1] = выделенные вершины в порядке топсорта
// проверяем, что p[0]==v1, p[k-1]==vk, иначе ответ 0
long long ans = 1;
vector<long long> dp(n, 0); // один раз, а не на каждый отрезок
for (int i = 0; i + 1 < k; ++i) {
// границы в массиве order: от pos[p[i]] до pos[p[i+1]]
for (int j = pos[p[i]]; j <= pos[p[i + 1]]; ++j)
dp[order[j]] = 0; // сбрасываем только свой отрезок: O(длина отрезка)
dp[p[i + 1]] = 1; // база
for (int j = pos[p[i + 1]] - 1; j >= pos[p[i]]; --j) {
int v = order[j];
for (int u : g[v])
if (pos[u] <= pos[p[i + 1]])
dp[v] = (dp[v] + dp[u]) % MOD;
}
ans = ans * dp[p[i]] % MOD;
if (ans == 0) break;
}Задача 10. Дан взвешенный DAG на $n$ вершинах и $m$ рёбрах. Найти сумму длин всех простых путей по модулю (длина пути — сумма весов его рёбер).
Идея учёта по рёбрам. Вместо суммирования по путям, просуммируем по рёбрам их вклад:
Путь проходит через ребро $u \to v$ тогда и только тогда, когда некоторый путь заканчивается в $u$ и некоторый путь начинается в $v$; эти части независимы. Значит,
где $\mathrm{cnt\_out}[v]$ — число путей, начинающихся в $v$ (включая тривиальный путь из одной вершины), а $\mathrm{cnt\_in}[u]$ — число путей, заканчивающихся в $u$ (тоже включая тривиальный).
Пересчёт. Считаем по топсорту:
Первое — идём справа налево (или в обратном топсорте), второе — по обратному графу. «Единица» — это тривиальный путь из самой вершины (длина 0). Тогда ответ
vector<long long> cntOut(n, 0), cntIn(n, 0);
// cntOut по обратному топсорту
for (int i = n - 1; i >= 0; --i) {
int v = order[i];
cntOut[v] = 1;
for (int u : g[v])
cntOut[v] = (cntOut[v] + cntOut[u]) % MOD;
}
// cntIn по графу gr (обратному) и прямому топсорту
for (int i = 0; i < n; ++i) {
int v = order[i];
cntIn[v] = 1;
for (int u : gr[v])
cntIn[v] = (cntIn[v] + cntIn[u]) % MOD;
}
long long ans = 0;
for (auto [u, v, w] : edges)
ans = (ans + (long long)w % MOD * cntIn[u] % MOD * cntOut[v]) % MOD;| Понятие / алгоритм | Идея | Сложность |
|---|---|---|
| Времена входа-выхода | счётчик при входе и выходе DFS | $O(V+E)$ |
| Вложенность $[\mathrm{tin},\mathrm{tout}]$ | интервалы вложены или не пересекаются; $u$ предок $v \iff \mathrm{tin}[u]\le\mathrm{tin}[v],\ \mathrm{tout}[v]\le\mathrm{tout}[u]$ | $O(1)$ проверка |
| Топсорт | порядок убывания $\mathrm{tout}$; на практике — push_back при выходе и reverse | $O(V+E)$ |
| Существование топсорта | есть $\iff$ граф ациклический | — |
| Компоненты связности | DFS + покраска | $O(V+E)$ |
| КСС (Косарайю) | DFS → порядок по $\mathrm{tout}$; в обратном графе красим по убыванию $\mathrm{tout}$ | $O(V+E)$ |
| Конденсация | сжать КСС, рёбра между компонентами; всегда DAG | $O(V+E)$ |
| Высота поддерева | $dp[v]=\max(dp[u]+1)$ | $O(n)$ |
| Диаметр дерева | два максимума спусков: $\max(d[u],\ down[u]{+}1,\ x{+}y{+}2)$ | $O(n)$ |
| Максимальное независимое множество | $dp_0, dp_1$ по состояниям «взяли / не взяли» | $O(n)$ |
| Длиннейший путь в DAG | ДП справа налево по топсорту | $O(V+E)$ |