Занятие состоит из двух частей: разбор контеста по дереву отрезков (его задачи были на предыдущем занятии) и лекция по графам — DFS и всё, что из него вытекает: мосты и точки сочленения, нечётные циклы, эйлеров путь, топологическая сортировка, компоненты сильной связности, 2-SAT и круглоквадратное дерево. Код ко всем приведённым алгоритмам проверен случайными тестами против перебора.
В записи разобраны задачи G, H, A, K, J; остальные уже разбирались на семинаре предыдущего занятия. Условия на записи пересказываются устно.
16:50 Условие. На плоскости даны горизонтальные и вертикальные отрезки; нужно посчитать их объединение (ниже — число целых точек в объединении, концы включены; в записи это «посчитать объединение»). Лектор замечает, что аналогичная задача для объединения прямоугольников требует дерева отрезков с массовыми операциями.
17:32 Идея. (1) Склеиваем перекрывающиеся отрезки на одной прямой — по каждой вертикали и каждой горизонтали стандартным сканированием. Теперь на каждой прямой отрезки не пересекаются. (2) Формула включений-исключений для двух множеств: $|A\cup B|=|A|+|B|-|A\cap B|$ — «объединение и пересечение часто двойственны, обычно считать одно из них проще». Здесь $A$ — горизонтальные, $B$ — вертикальные отрезки. (3) После склейки любая пара «горизонтальный + вертикальный» пересекается не более чем в одной точке, поэтому $|A\cap B|$ — это просто число пересекающихся пар.
19:57 Сканирование. Идём по $x$ слева направо с деревом (Фенвиком) по $y$. Начало горизонтального отрезка — прибавляем 1 в его $y$, конец — вычитаем. Для вертикального отрезка в точке $x$ запрашиваем сумму по $y\in[y_1,y_2]$: это число ещё «не закончившихся» горизонтальных отрезков, которые он пересекает. Координаты можно сжать — от этого решение не меняется. При равных $x$ добавления и удаления нужно обрабатывать раньше запросов.
// Сколько целых точек покрыто объединением горизонтальных и вертикальных отрезков (концы включены).
struct Seg { int x1, y1, x2, y2; };
long long unionSize(const vector<Seg> &segs) {
map<int, vector<pair<int,int>>> hor, ver; // горизонтальные по y, вертикальные по x
for (auto s : segs) {
if (s.y1 == s.y2) hor[s.y1].push_back({min(s.x1, s.x2), max(s.x1, s.x2)}); // точка считается горизонтальным отрезком
else ver[s.x1].push_back({min(s.y1, s.y2), max(s.y1, s.y2)});
}
auto mergeAll = [](map<int, vector<pair<int,int>>> &m) { // на каждой прямой объединяем пересекающиеся отрезки
for (auto &[line, v] : m) {
sort(v.begin(), v.end());
vector<pair<int,int>> r;
for (auto p : v) { if (!r.empty() && p.first <= r.back().second) r.back().second = max(r.back().second, p.second); else r.push_back(p); }
v = r;
}
};
mergeAll(hor); mergeAll(ver);
long long total = 0;
for (auto &[l, v] : hor) for (auto p : v) total += p.second - p.first + 1;
for (auto &[l, v] : ver) for (auto p : v) total += p.second - p.first + 1;
// |A ∪ B| = |A| + |B| − |A ∩ B|; после склейки горизонтальный и вертикальный отрезки пересекаются не более чем в одной точке
vector<int> ys;
for (auto &[y, v] : hor) ys.push_back(y); // сжатие по y (достаточно y горизонтальных)
struct Ev { int x, type, a, b; }; // type 0: горизонтальный начался (+1 в y), 1: закончился (−1), 2: запрос вертикального
vector<Ev> ev;
for (auto &[y, v] : hor) for (auto p : v) { ev.push_back({p.first, 0, y, y}); ev.push_back({p.second + 1, 1, y, y}); }
for (auto &[x, v] : ver) for (auto p : v) ev.push_back({x, 2, p.first, p.second});
sort(ev.begin(), ev.end(), [](const Ev &l, const Ev &r) { return make_pair(l.x, l.type) < make_pair(r.x, r.type); }); // сначала добавления/удаления, потом запросы
int m = ys.size();
vector<int> bit(m + 1, 0);
auto add = [&](int i, int d) { for (i++; i <= m; i += i & -i) bit[i] += d; };
auto pref = [&](int i) { int r = 0; for (; i > 0; i -= i & -i) r += bit[i]; return r; };
long long cross = 0;
for (auto &e : ev) {
if (e.type < 2) add(lower_bound(ys.begin(), ys.end(), e.a) - ys.begin(), e.type == 0 ? 1 : -1);
else cross += pref(upper_bound(ys.begin(), ys.end(), e.b) - ys.begin()) - pref(lower_bound(ys.begin(), ys.end(), e.a) - ys.begin());
}
return total - cross;
}22:25 Условие (по записи). Дан массив $a_1,\dots,a_n$ (значения до $10^{18}$), запросы: заменить $a_i$ на $x$. Нужно находить самую длинную последовательность, которая сначала возрастает, потом убывает.
23:11 Идея. Перейдём от сравнения чисел к сравнению соседей: между $a_i$ и $a_{i+1}$ пишем символ роста, спада или равенства. «Сначала возрастает, потом убывает» превращается в «сначала символы роста, потом символы спада, без равенств» (в записи плюс — спад, минус — рост). Заменяя $a_i$, мы меняем лишь два символа — два точечных обновления. Задача похожа на «самая длинная серия нулей»: в вершине хранится семь значений — максимальные префикс и суффикс вида «рост$^*$ спад$^*$», максимальный префикс из одних спадов, максимальный суффикс из одних ростов, ответ внутри, флаги «весь отрезок из роста / из спада».
25:13 Слияние. Ответ через границу получается склейкой двух частей: суффикс левого, состоящий из одних ростов, + любой допустимый префикс правого; либо любой допустимый суффикс левого + префикс правого из одних спадов. Остальные поля пересчитываются как в «нулях».
// Самый длинный «горб» (строго возрастает, затем строго убывает) среди подотрезков массива. Сравниваем соседей: U — рост, D — спад, E — равенство.
// Нужна самая длинная подстрока вида U*D* без E. Узел дерева хранит 7 величин.
struct Node {
int len = 0;
int pre = 0, suf = 0; // самый длинный префикс / суффикс вида U*D*
int preD = 0, sufU = 0; // самый длинный префикс из одних D / суффикс из одних U
int best = 0; // лучшая подстрока внутри
bool allU = true, allD = true; // весь отрезок из U / весь из D (пустой отрезок — оба true)
};
Node merge(const Node &a, const Node &b) {
Node r;
r.len = a.len + b.len;
r.allU = a.allU && b.allU; r.allD = a.allD && b.allD;
// префикс U*D*: если левая часть — одни U, префикс может продолжиться любым префиксом U*D* справа; если левая U*D*, но не одни U — только префиксом из D
if (a.allU) r.pre = a.len + b.pre;
else if (a.pre == a.len) r.pre = a.len + b.preD;
else r.pre = a.pre;
if (b.allD) r.suf = b.len + a.suf;
else if (b.suf == b.len) r.suf = b.len + a.sufU;
else r.suf = b.suf;
r.preD = a.allD ? a.len + b.preD : a.preD;
r.sufU = b.allU ? b.len + a.sufU : b.sufU;
// через границу: (суффикс левой из одних U) + (любой префикс U*D* правой) либо (любой суффикс U*D* левой) + (префикс из одних D)
r.best = max({a.best, b.best, a.sufU + b.pre, a.suf + b.preD});
return r;
}
Node leaf(int type) { // type: 0 = U, 1 = D, 2 = E
Node r; r.len = 1;
r.allU = type == 0; r.allD = type == 1;
r.pre = r.suf = r.best = (type != 2);
r.preD = (type == 1); r.sufU = (type == 0);
return r;
}
int typeOf(long long x, long long y) { return x < y ? 0 : (x > y ? 1 : 2); }
// Ответ для всего массива из n >= 1 чисел: best + 1 (число элементов горба), для n = 1 — 1.26:39 Условие. Прямоугольник $V\times H$ без пробелов выложен квадратами (возможно, разного размера); квадраты стёрли, остались центры. Нужно восстановить сами квадраты. Лектор отмечает, что это одна задача, решаемая двумя способами (с неявным деревом и с set).
27:22 Идея. Центр квадрата либо целый, либо полуцелый, поэтому умножаем все координаты на два. Сортируем центры по $x$ и идём слева направо. Для первого квадрата слева нет других квадратов, поэтому его левая сторона — граница прямоугольника, а так как он квадрат, сторона определена. В общем случае храним «профиль»: для каждой строки (по $y$) — $x$ левой границы свободной области. Квадрат с центром $(X,Y)$: на уровне $Y$ профиль равен $x_{\text{лев}}$ (все квадраты левее уже обработаны — их центры левее), поэтому полусторона $h=X-x_{\text{лев}}$. После этого на строках $[Y-h,\,Y+h)$ профиль сдвигается на $2h$ — одинаково для всех этих строк, так как в них не было пробелов. Итого операции «прибавить на отрезке» и «значение в точке».
31:18 Альтернатива с set. Хранить отрезки строк с одинаковым значением границы; присваивание на отрезке заменяет несколько отрезков одним — амортизированно мало операций (одна операция может сделать много действий, но суммарно их мало).
// Прямоугольник без пробелов выложен квадратами. Известны центры (координаты удвоены, чтобы все были целыми). Восстановить стороны.
// Идём по возрастанию x центра. fen хранит для каждой строки (в удвоенных координатах) x левой границы «ещё не занятой» области.
struct Fen { // прибавление на отрезке, значение в точке
int n; vector<long long> t;
Fen(int n) : n(n), t(n + 2, 0) {}
void addRange(int l, int r, long long x) { upd(l, x); upd(r + 1, -x); } // строки l..r
void upd(int i, long long x) { for (i++; i <= n + 1; i += i & -i) t[i] += x; }
long long get(int i) { long long s = 0; for (i++; i > 0; i -= i & -i) s += t[i]; return s; }
};
// centers: пары (X, Y) в удвоенных координатах, height2 = 2·H. Возвращает сторону (в исходных единицах) для каждого центра по порядку ввода.
vector<long long> restoreSquares(int height2, const vector<pair<long long,long long>> ¢ers) {
int m = centers.size();
vector<int> ord(m); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) { return centers[a].first < centers[b].first; });
Fen f(height2);
vector<long long> side(m);
for (int id : ord) {
auto [X, Y] = centers[id];
long long left = f.get((int)Y); // левая граница свободной области на уровне центра — левая сторона квадрата
long long h = X - left; // полусторона в удвоенных единицах = сторона в исходных
side[id] = h;
f.addRange((int)(Y - h), (int)(Y + h - 1), 2 * h); // теперь на этих строках граница сдвинулась до правой стороны квадрата
}
return side;
}35:03 Условие (по записи). Дан массив из $n\le10^5$ чисел, $a_i\le10^6$. Посчитать число способов разбить его на подотрезки $[L_1,R_1],[L_2,R_2],\dots$ так, чтобы $f(L_1,R_1)\le f(L_2,R_2)\le\dots$, где $f$ — побитовое OR на отрезке. Лектор: «каждый раз, когда элементы не до $10^9$, это неспроста».
35:48 Динамика. $dp_{i,u}$ — число способов разбить префикс длины $i$ так, что у последнего отрезка $f=u$. Переход: $dp_{i,u}=\sum_{j:\ \mathrm{OR}(j+1..i)=u}\ \sum_{v\le u}dp_{j,v}$. Проблема — много значений $u$ и большая сумма.
38:13 Ключевое замечание. OR отрезка с фиксированным левым или правым концом — неубывающая цепочка, и при каждом увеличении добавляется хотя бы один бит, поэтому различных значений не больше $\log_2 a+1\le21$. (Тот же приём работает для НОД: при изменении он уменьшается хотя бы вдвое.) Поэтому для фиксированного конца отрезки разбиваются на $\le21$ блоков с одинаковым OR.
45:18 Динамика вперёд. Лектор сначала (41:55) описывает сумму по прямоугольнику $[l,r]\times[0,u]$ в плоскости (начало, значение) офлайн с Фенвиком, затем предлагает проще — перейти к «динамике вперёд». Когда $dp_j$ посчитана, для каждого блока значений OR отрезков, начинающихся в $j+1$ (их $\le21$), вычисляем $S=\sum_{v\le u}dp_{j,v}$ — сумма по маленькому списку — и прибавляем $S$ к ответам $dp_{i,u}$ сразу для всех $i$ блока: это «прибавление на отрезке индексов $i$ для значения $u$». Блоки находятся по позициям следующего вхождения каждого бита (бинпоиск по ним, как в записи, не нужен). Прибавление на отрезке реализуется событиями «добавить/убрать вклад» в позициях начала и конца блока. Время $O(n\cdot B\log B)$, $B=20$.
Лектор подчёркивает: динамика вперёд и назад — одно и то же, различается только то, что удобнее: «собирать сумму из прошлых состояний» или «раскладывать значение состояния по будущим».
// Число разбиений массива на отрезки так, чтобы побитовые OR отрезков не убывали: OR_1 <= OR_2 <= ... (по модулю MOD). a_i < 2^B.
// dp[j] — маленький список (значение OR последнего отрезка, число способов) для префикса длины j. «Динамика вперёд» из j.
const long long MOD = 998244353;
const int B = 20;
long long countOrSplits(const vector<int> &a0) {
int n = a0.size();
vector<int> a(n + 2, 0);
for (int i = 0; i < n; i++) a[i + 1] = a0[i];
vector<vector<int>> nxt(B, vector<int>(n + 3, n + 1)); // nxt[k][s] — первая позиция >= s, где установлен бит k
for (int k = 0; k < B; k++)
for (int s = n; s >= 1; s--) nxt[k][s] = (a[s] >> k & 1) ? s : nxt[k][s + 1];
struct Ev { int x; long long d; int c; };
vector<vector<Ev>> events(n + 3); // события «добавить/убрать вклад для значения x» в позиции i
map<int, pair<long long,int>> cur; // x -> (сумма вкладов, число активных вкладов)
vector<pair<int,long long>> dp = {{0, 1}}; // dp[0]: пустой префикс, «OR» = 0 (подходит под любой следующий)
for (int j = 0; j <= n; j++) {
if (j >= 1) {
for (auto &e : events[j]) { // применяем события в позиции j
auto &p = cur[e.x];
p.first = ((p.first + e.d) % MOD + MOD) % MOD; p.second += e.c;
if (p.second == 0) cur.erase(e.x);
}
dp.clear();
for (auto &[x, p] : cur) dp.push_back({x, p.first}); // dp[j]: OR последнего отрезка = x
}
if (j == n) break;
int s = j + 1;
vector<int> pos; // позиции, где в OR(s..i) появляется новый бит
for (int k = 0; k < B; k++) if (nxt[k][s] <= n) pos.push_back(nxt[k][s]);
sort(pos.begin(), pos.end()); pos.erase(unique(pos.begin(), pos.end()), pos.end());
int curOr = 0, start = s;
auto emit = [&](int l, int r, int orv) { // для i в [l, r] отрезок (j, i] имеет OR = orv
long long S = 0;
for (auto &[v, c] : dp) if (v <= orv) S = (S + c) % MOD; // суммируем dp[j][v] по v <= orv
events[l].push_back({orv, S, 1}); events[r + 1].push_back({orv, (MOD - S) % MOD, -1});
};
for (int p : pos) {
if (p > start) emit(start, p - 1, curOr);
curOr |= a[p]; start = p;
}
emit(start, n, curOr);
}
long long ans = 0;
for (auto &[v, c] : dp) ans = (ans + c) % MOD;
return ans;
}52:40 Условие (по записи). Запросы трёх видов: добавить человека, который придёт в момент $t$ и займёт кабинет на время $d$; удалить такого человека; спросить, сколько придётся ждать, если прийти в момент $T$ (после всех, кто пришёл раньше). Пример: приходят в 2 (занимает 3 с) и в 4 (занимает 2 с); тот, кто придёт в 5, дождётся освобождения в момент 7. Будем считать, что люди обслуживаются в порядке прихода, а ждать нужно $\max(0,\ \text{время освобождения}-T)$.
54:06 В лоб. Пусть $f$ — время освобождения кабинета; перебираем людей по возрастанию $t_i$: $f\leftarrow\max(f,t_i)+d_i$ (если кабинет свободен, человек ждёт до $t_i$). Ответ — итоговое $f$.
55:09 Способ 1 (через максимум и суммы). Рассмотрим последний момент «свободы» перед приходом: человек $x$ пришёл в $t_x$ и после него кабинет был занят без перерывов до конца. Тогда $f=t_x+\sum_{j\ge x}d_j$ (суммы по людям с $t_j<T$), и это максимум по всем $x$ такого выражения. Значит, в дереве нужно хранить $t_x+\sum_{j\ge x}d_j$ — при добавлении $d$ человеку с индексом $i$ ко всем $x\le i$ прибавляется $d$ (массовая операция) — и брать максимум на префиксе. Лишние слагаемые от людей, пришедших после $T$, вычитаем отдельным деревом сумм. Лектор отмечает, что такая запись допустима лишь с массовыми операциями.
1:03:19 Способ 2 (функциональный, без массовых операций). Каждый человек — функция «время освобождения до → после»: $s\mapsto\max(s,t)+d=\max(s+d,\ t+d)$. Композиция двух функций вида $s\mapsto\max(s+A,B)$ снова такого вида: после $(A_1,B_1)$, затем $(A_2,B_2)$ получаем $(A_1+A_2,\ \max(B_1+A_2,B_2))$ — это ассоциативно, поэтому подходит для дерева отрезков. Дерево строится по моментам прихода (сжатым); добавление и удаление человека — точечное изменение листа (удалённый — тождественная функция). Запрос: композиция листьев с $t<T$, применённая к $s=0$. Лектор так формулирует главную мысль: в вершине дерева отрезков можно хранить не только числа, но и функции (или перестановки), лишь бы их композиция была ассоциативной.
// Очередь: человек приходит в момент t и занимает кабинет на d. Обслуживают в порядке прихода. Запрос T: когда освободится кабинет после всех, кто пришёл раньше T.
// Каждый человек — функция s -> max(s + d, t + d) = max(s + A, B); композиция таких функций — снова такая же функция: дерево отрезков над функциями.
const long long NEG = LLONG_MIN / 4;
struct F { long long A, B; }; // s -> max(s + A, B)
F compose(F f, F g) { return {f.A + g.A, max(f.B + g.A, g.B)}; } // сначала f, потом g
const F IDENT = {0, NEG};
struct QueueTree {
int n; vector<F> t; vector<long long> times; // times — отсортированные возможные моменты прихода
QueueTree(vector<long long> ts) : times(ts) {
sort(times.begin(), times.end());
n = 1; while (n < (int)times.size()) n <<= 1;
t.assign(2 * n, IDENT);
}
void set(long long arrive, long long dur, bool present) {
int i = lower_bound(times.begin(), times.end(), arrive) - times.begin() + n;
t[i] = present ? F{dur, arrive + dur} : IDENT;
for (i >>= 1; i; i >>= 1) t[i] = compose(t[2 * i], t[2 * i + 1]);
}
long long waitFrom(long long T) { // сколько ждать, если прийти в момент T
int r = lower_bound(times.begin(), times.end(), T) - times.begin(); // берём тех, кто пришёл строго раньше T
F acc = IDENT;
// композиция левого префикса [0, r): обход снизу вверх, левые куски накапливаем слева направо
vector<int> leftNodes, rightNodes;
for (int l = n, rr = n + r; l < rr; l >>= 1, rr >>= 1) {
if (l & 1) leftNodes.push_back(l++);
if (rr & 1) rightNodes.push_back(--rr);
}
for (int v : leftNodes) acc = compose(acc, t[v]);
for (int k = (int)rightNodes.size() - 1; k >= 0; k--) acc = compose(acc, t[rightNodes[k]]);
long long freeAt = max(0LL + acc.A, acc.B); // начальное свободное время 0
return max(0LL, freeAt - T);
}
};1:16:49 План: что даёт DFS; мосты и точки сочленения; нечётные циклы; эйлеров цикл и путь; затем ориентированные графы (топологическая сортировка, компоненты сильной связности), 2-SAT и вершинная двусвязность. Предполагается, что DFS слушатели уже знают.
1:17:51 Обход графа поиском в глубину строит дерево DFS (у каждой вершины, кроме корня, есть предок). Остальные рёбра графа делятся на два типа: ребро между предком и потомком (необязательно непосредственным) называется вертикальным, любое другое — горизонтальным (общий предок концов не совпадает ни с одним из них).
1:18:53 Утверждение. В неориентированном графе при обходе DFS горизонтальных рёбер нет.
Доказательство. Пусть $uv$ — ребро, и обработка $u$ началась раньше, чем $v$. Пока DFS не завершил $u$, он обязательно рассмотрит ребро $uv$ и либо войдёт в $v$ (тогда $v$ — потомок $u$), либо $v$ уже был посещён внутри обработки $u$ (тоже потомок), — иначе DFS завершил бы $u$, не пройдя по ребру. В любом случае $u$ — предок $v$, ребро вертикальное.
1:42:30 Таким образом, DFS «убирает» неудобные рёбра. BFS, напротив, делит вершины на слои, и у него нет вертикальных рёбер, кроме рёбер дерева (лишнее ребро всегда соединяет вершины одного слоя или соседних слоёв); поэтому приёмы ниже на BFS не переносятся (1:33:16: из поддерева BFS рёбра могут идти «вбок»).
1:19:58 Определения. Мост — ребро, при удалении которого число компонент связности увеличивается. Точка сочленения — вершина с тем же свойством.
1:21:49 Мосты. Рассмотрим ребро дерева $(p,v)$. Из поддерева $v$ в остальной граф идут только вертикальные рёбра — в $v$ или в предков (горизонтальных нет). Значит, это ребро — мост ⇔ из поддерева $v$ нет ни одного ребра (кроме самого $(p,v)$) в $p$ или выше. Определим для вершины $v$ величину $up_v$ — минимальную глубину, в которую можно попасть из поддерева $v$ одним шагом по ребру, не равному ребру, по которому мы пришли в $v$. Пересчёт: минимум по всем детям и по всем рёбрам вершины $v$ (кроме ребра в родителя): $up_v=\min\bigl(depth_v,\ \min_{c}up_c,\ \min_{(v,w)}depth_w\bigr)$. Ребро $(p,v)$ — мост ⇔ $up_v\ge depth_v$, то есть подняться выше $v$ нельзя.
1:30:10 Точки сочленения (тот же DFS, анализ при выходе из вершины). Для некорневой вершины $v$: если у какого-то ребёнка $c$ $up_c\ge depth_v$, то поддерево $c$ отвалится при удалении $v$ — $v$ точка сочленения. Для корня: «сверху ничего нет», поэтому корень — точка сочленения ⇔ у него не менее двух детей в дереве DFS (дети не связаны рёбрами между собой — горизонтальных рёбер нет).
// Мосты и точки сочленения одним DFS, O(n + m). Рёбра различаем по номеру, поэтому кратные рёбра обрабатываются верно.
struct Graph {
int n;
vector<vector<pair<int,int>>> adj; // (сосед, номер ребра)
vector<pair<int,int>> edges;
Graph(int n) : n(n), adj(n) {}
void addEdge(int a, int b) { adj[a].push_back({b, (int)edges.size()}); adj[b].push_back({a, (int)edges.size()}); edges.push_back({a, b}); }
};
struct Cut {
vector<int> depth, up; // up[v] — минимальная глубина, достижимая из поддерева v одним обратным ребром
vector<char> isBridge, isCut;
Cut(const Graph &g) : depth(g.n, -1), up(g.n), isBridge(g.edges.size(), 0), isCut(g.n, 0) {
for (int v = 0; v < g.n; v++) if (depth[v] < 0) { depth[v] = 0; dfs(g, v, -1); }
}
void dfs(const Graph &g, int v, int parentEdge) { // parentEdge — НОМЕР ребра, по которому пришли в v
up[v] = depth[v];
int children = 0;
for (auto [to, id] : g.adj[v]) {
if (id == parentEdge) continue; // не ходим назад по тому же ребру (но параллельное ребро — другой номер!)
if (depth[to] >= 0) { up[v] = min(up[v], depth[to]); continue; } // обратное ребро вверх
depth[to] = depth[v] + 1;
dfs(g, to, id); children++;
up[v] = min(up[v], up[to]);
if (up[to] >= depth[to]) isBridge[id] = 1; // из поддерева to не подняться выше v по другому ребру
if (parentEdge >= 0 && up[to] >= depth[v]) isCut[v] = 1; // поддерево to отвалится при удалении v
}
if (parentEdge < 0 && children >= 2) isCut[v] = 1; // корень — точка сочленения, если у него два и более сына
}
};1:44:41 Граф без нечётных циклов двудольный, и наоборот. Красим вершины DFS-ом в два цвета: у потомка цвет, противоположный родителю. Если встретился сосед того же цвета — найден нечётный цикл. Чтобы его выписать, храним стек рекурсии (вершины на пути от корня к текущей). Сосед того же цвета уже посещён и (из-за отсутствия горизонтальных рёбер) лежит на стеке; снимаем вершины со стека, пока не дойдём до него: получившийся путь вместе с рёбром — цикл. Его длина нечётна, так как цвета двух концов пути одинаковы (глубины одной чётности), и ребро замыкает путь чётной длины.
// Нечётный цикл: красим граф в два цвета DFS-ом, стек вершин хранится в path. Возвращает вершины цикла нечётной длины или пустой список.
bool findOdd(const vector<vector<int>> &g, int v, int p, vector<int> &color, vector<int> &path, vector<int> &cycle) {
color[v] = (p < 0) ? 1 : 3 - color[p]; // цвета 1 и 2: у потомка цвет противоположный родителю
path.push_back(v);
for (int to : g[v]) {
if (to == p) continue;
if (color[to] == 0) { if (findOdd(g, to, v, color, path, cycle)) return true; }
else if (color[to] == color[v]) { // сосед того же цвета; он уже на стеке path — снимаем вершины до него
int i = (int)path.size() - 1;
while (path[i] != to) i--;
cycle.assign(path.begin() + i, path.end());
return true;
}
}
path.pop_back();
return false;
}
vector<int> oddCycle(const vector<vector<int>> &g) {
int n = g.size();
vector<int> color(n, 0), path, cycle;
for (int v = 0; v < n; v++) if (!color[v] && findOdd(g, v, -1, color, path, cycle)) return cycle;
return {};
}1:48:50 Определения. Эйлеров цикл — цикл, проходящий по каждому ребру ровно один раз; эйлеров путь — то же без требования совпадения начала и конца.
1:49:11 Критерий (неориентированный граф). Эйлеров цикл существует ⇔ (1) степени всех вершин чётны и (2) все рёбра лежат в одной компоненте связности (изолированные вершины не мешают).
Необходимость. В цикле в каждую вершину входят и выходят одинаковое число раз (начало и конец — одна вершина), значит степень чётна; все рёбра соединены одним обходом.
1:53:25 Достаточность — алгоритм. Рекурсивная процедура: пока у $v$ остались рёбра, берём ребро $(v,u)$, удаляем его из графа, вызываем процедуру от $u$ и после этого добавляем $v$ в ответ. Рассуждение: выйдя из $v$ по ребру, мы получаем ровно две вершины нечётной степени ($v$ и $u$); пока гуляем по оставшимся рёбрам, мы можем выйти из любой вершины, в которую зашли (степень там была чётна, а стала нечётна, то есть положительна), поэтому закончим только вернувшись в начало. Если при этом остались не пройденными рёбра, то в силу связности они выходят из какой-то вершины построенного цикла; оператор while по рёбрам вершины подцепит новый цикл при откате. Образно: нашли цикл, откатились назад, нашли ещё один, и так далее.
2:01:06 Ребро нужно удалять сразу, как прошли (флагом по номеру ребра или удалением из списка); если вместо этого помечать, при каждом заходе в вершину придётся заново просматривать список — получится квадратичное время. Рёбра в ответе лежат в обратном порядке; для неориентированного графа это безразлично.
2:04:10 Эйлеров путь. Тот же критерий, но допускается ровно две вершины нечётной степени: они — концы пути. Способ из записи: добавить между ними фиктивное ребро, найти цикл и удалить его. Эквивалентно: запустить тот же алгоритм прямо из вершины с нечётной степенью. Если нечётных вершин больше двух, пути нет — кроме концов, в каждую вершину нужно заходить и выходить поровну.
// Алгоритм Хирхольцера (итеративный): стек вершин, рёбра удаляются сразу при проходе. O(n + m).
// Возвращает вершины в порядке обхода всех рёбер; пустой результат — обход невозможен.
vector<int> euler(int n, const vector<pair<int,int>> &edges, int start) {
vector<vector<pair<int,int>>> adj(n);
for (int i = 0; i < (int)edges.size(); i++) {
adj[edges[i].first].push_back({edges[i].second, i});
adj[edges[i].second].push_back({edges[i].first, i});
}
vector<char> used(edges.size(), 0);
vector<int> ptr(n, 0), stack{start}, res;
while (!stack.empty()) {
int v = stack.back();
while (ptr[v] < (int)adj[v].size() && used[adj[v][ptr[v]].second]) ptr[v]++; // пропускаем уже пройденные рёбра
if (ptr[v] == (int)adj[v].size()) { res.push_back(v); stack.pop_back(); continue; } // из v выходить некуда — вершина идёт в ответ
auto [to, id] = adj[v][ptr[v]];
used[id] = 1; // ребро удалено сразу, как только прошли
stack.push_back(to);
}
if (res.size() != edges.size() + 1) return {}; // не все рёбра достижимы из start (граф «несвязен»)
reverse(res.begin(), res.end()); // для цикла порядок безразличен, для пути — от start до конца
return res;
}
// Критерий: цикл существует ⇔ все степени чётны и рёбра связны; путь ⇔ нечётных вершин 0 или 2 (старт — в нечётной).
vector<int> eulerCycleOrPath(int n, const vector<pair<int,int>> &edges, bool wantCycle) {
if (edges.empty()) return {};
vector<int> deg(n, 0), odd;
for (auto &e : edges) { deg[e.first]++; deg[e.second]++; }
for (int v = 0; v < n; v++) if (deg[v] % 2) odd.push_back(v);
if (wantCycle ? !odd.empty() : (odd.size() != 0 && odd.size() != 2)) return {};
int start = (!wantCycle && !odd.empty()) ? odd[0] : edges[0].first;
return euler(n, edges, start);
}3:10:43 В неориентированном графе отношение «из $a$ есть путь в $b$» рефлексивно, транзитивно и симметрично, поэтому разбивает граф на компоненты связности. В ориентированном графе симметричность теряется: из $a$ путь в $b$ есть, обратно может не быть. Цель — подобрать замену отношению «равно», которая снова даёт осмысленные классы.
3:24:13 Назовём вершины эквивалентными, если есть путь из $a$ в $b$ и из $b$ в $a$. Это отношение эквивалентности, его классы — компоненты сильной связности (КСС).
3:13:09 Ориентированный ациклический граф (DAG) — граф без ориентированных циклов; дерево — самый простой пример. Задача: занумеровать вершины так, чтобы все рёбра шли от меньшего номера к большему. Это даёт порядок пересчёта динамики на графе и позволяет «видеть DAG как усложнённый массив».
3:17:17 Алгоритм. Запускаем DFS и в конце обработки каждой вершины кладём её в массив; затем разворачиваем массив. Время выхода из вершины называют tout, время входа — tin.
3:18:43 Корректность. Пусть есть ребро $v\to u$. Когда мы выходим из $v$, мы уже обработали это ребро, значит, $u$ либо уже обработана и положена в массив раньше $v$, либо лежит на стеке выше (в этом случае она будет положена раньше $v$, потому что стек разматывается с вершины). Оба случая дают: $u$ в массиве раньше $v$, после разворота — позже. Если DAG не ацикличен, этот порядок не годится; проверить это можно, пройдя по всем рёбрам и найдя «плохое» ребро (в рекурсии — ребро в вершину, лежащую на стеке) (3:20:03).
3:24:53 Алгоритм. (1) Строим обратный граф $G'$ (рёбра развёрнуты). (2) Запускаем в нём тот же DFS, записывая вершины в порядке выхода, и разворачиваем массив $T$ — «топсорт» $G'$ (на самом деле просто сортировка по убыванию времени выхода; циклов может быть, и это не настоящий топсорт). (3) Идём по вершинам в порядке $T$; из каждой ещё не окрашенной вершины запускаем обычный DFS в исходном графе $G$ и красим всё достигнутое в новый цвет — это одна компонента.
3:28:24 Корректность. Пусть $i$ — корень очередного обхода, $j$ покрашена в его цвет. Из $i$ в $j$ есть путь в $G$ (это обход по $G$); надо доказать, что из $j$ есть путь в $i$. Заметим, что $i$ стоит в $T$ раньше $j$ (иначе $j$ была бы корнем раньше или уже окрашена), то есть в DFS по $G'$ время выхода у $i$ больше, чем у $j$. В $G'$ путь идёт из $j$ в $i$ (развёрнутый путь $i\to j$). Рассмотрим, кого из $i,j$ DFS по $G'$ посетил первым. Если $j$, то $i$ достижима из $j$, поэтому $i$ закончилась бы раньше $j$ (всё достижимое по непосещённым вершинам завершается до выхода из $j$) — противоречие. Значит, первой посещена $i$, и $j$ была посещена во время обработки $i$ (иначе $j$ закончилась бы после $i$), то есть $j$ достижима из $i$ в $G'$, а в $G$ есть путь $j\to i$. $\blacksquare$
// Компоненты сильной связности (алгоритм Косарайю в версии лекции): порядок выхода по обратному графу, затем обход прямого графа.
struct SCC {
int n, comps = 0;
vector<vector<int>> g, rg;
vector<int> comp, order;
vector<char> seen;
SCC(int n) : n(n), g(n), rg(n), comp(n, -1), seen(n, 0) {}
void addEdge(int a, int b) { g[a].push_back(b); rg[b].push_back(a); }
void dfs1(int v) { // обход обратного графа, вершину кладём в order при ВЫХОДЕ
seen[v] = 1;
for (int to : rg[v]) if (!seen[to]) dfs1(to);
order.push_back(v);
}
void dfs2(int v, int c) { // обычный обход прямого графа: всё достижимое окрашиваем в c
comp[v] = c;
for (int to : g[v]) if (comp[to] < 0) dfs2(to, c);
}
void run() {
for (int v = 0; v < n; v++) if (!seen[v]) dfs1(v);
reverse(order.begin(), order.end()); // убывание времени выхода
for (int v : order) if (comp[v] < 0) dfs2(v, comps++);
// номера компонент идут в порядке, ОБРАТНОМ топологическому порядку конденсации: comp 0 — «сток»
}
};
// топологическая сортировка DAG: порядок выхода из DFS, развёрнутый
vector<int> topSort(const vector<vector<int>> &g, bool &ok) {
int n = g.size();
vector<int> out, state(n, 0);
ok = true;
function<void(int)> dfs = [&](int v) {
state[v] = 1;
for (int to : g[v]) {
if (state[to] == 1) ok = false; // ребро в вершину на стеке — цикл
else if (state[to] == 0) dfs(to);
}
state[v] = 2; out.push_back(v);
};
for (int v = 0; v < n; v++) if (!state[v]) dfs(v);
reverse(out.begin(), out.end());
return out;
}3:42:47 Конденсация. Сожмём каждую КСС в одну вершину. Если сжимать обычные компоненты связности неориентированного графа, получится набор изолированных вершин — неинтересно. А КСС в орграфе дают DAG: цикл между компонентами означал бы, что они сливаются в одну КСС. На конденсации динамика считается по топсорту, внутри компоненты из любой вершины достижима любая.
3:47:27 Обозначения. Для булевых переменных: дизъюнкция $a\lor b$ («или»), конъюнкция $a\land b$ («и»), импликация $a\Rightarrow b$ (ложна только при $a=1,b=0$), отрицание $\lnot a$.
3:49:55 Задача. Даны булевы переменные $x_1,\dots,x_n$ и формула — конъюнкция дизъюнктов, в каждом ровно два литерала (переменная или её отрицание): $(x_1\lor\lnot x_3)\land(\lnot x_5\lor x_6)\land\dots$ Нужно выбрать значения, при которых формула истинна. Задача редко встречается явно, но часто получается сведением.
3:52:23 Граф импликаций. Дизъюнкт $a\lor b$ равносилен конъюнкции двух импликаций $\lnot a\Rightarrow b$ и $\lnot b\Rightarrow a$ (если $a$ ложно, то $b$ обязано быть истинным, и наоборот). Для каждой переменной заводим две вершины — «$x$» и «$\lnot x$»; для каждого дизъюнкта добавляем оба ребра. Тест: для дизъюнкта $(\lnot a_7\lor a_9)$ рёбра — $a_7\to a_9$ и $\lnot a_9\to\lnot a_7$.
3:57:50 Алгоритм. (1) Выделяем КСС в графе импликаций. (2) Топологически сортируем конденсацию; пусть $\mathrm{ord}(v)$ — номер компоненты вершины $v$ в этом порядке. (3) Для каждой переменной: если $\mathrm{ord}(x)=\mathrm{ord}(\lnot x)$ — решения нет; иначе $x=\text{false}$ при $\mathrm{ord}(x)<\mathrm{ord}(\lnot x)$ и $x=\text{true}$ при $\mathrm{ord}(x)>\mathrm{ord}(\lnot x)$.
4:00:00 Почему нет решения при $\mathrm{ord}(x)=\mathrm{ord}(\lnot x)$. Тогда есть пути $x\to\lnot x$ и $\lnot x\to x$. Импликации транзитивны: из $x\Rightarrow\lnot x$ следует $x=0$, а из $\lnot x\Rightarrow x$ следует $x=1$ — противоречие.
4:05:50 Корректность. Допустим, дизъюнкт $a\lor b$ не выполнен: $a=0$ и $b=0$ (под $a$, $b$ понимаются вершины графа — переменные или их отрицания). По правилу присваивания $\mathrm{ord}(a)<\mathrm{ord}(\lnot a)$ и $\mathrm{ord}(b)<\mathrm{ord}(\lnot b)$. Ребра $\lnot a\to b$ и $\lnot b\to a$ дают $\mathrm{ord}(\lnot a)\le\mathrm{ord}(b)$ и $\mathrm{ord}(\lnot b)\le\mathrm{ord}(a)$. Цепочка:
то есть $\mathrm{ord}(a)<\mathrm{ord}(a)$ — противоречие. Значит, все дизъюнкты выполнены. Любой топологический порядок подходит, лишь бы он был одним на все переменные (4:04:42).
4:13:27 Что выражается через 2-SAT. Любая булева функция от двух переменных: $a\land b$ — задать $a=b=1$ (два дизъюнкта $(a\lor a)$, $(b\lor b)$); $a\oplus b$ — $(a\lor b)\land(\lnot a\lor\lnot b)$ («хотя бы одна единица и хотя бы один ноль»); $a\Rightarrow b$ — $(\lnot a\lor b)$. Через три и более переменных «или» — уже NP-полная задача (3-SAT). Но можно вводить дополнительные переменные.
4:16:14 Условие «не более одной единицы среди множества». Прямой способ — по дизъюнкту $(\lnot x_i\lor\lnot x_j)$ на каждую пару — даёт $O(k^2)$ дизъюнктов. С дополнительными префиксными переменными $p_i$ («среди $x_0..x_i$ есть единица») получается $O(k)$:
Обсуждение на записи (4:18:40) шло о схожей идее с разбиением на пары как в дереве отрезков (даёт $O(k\log k)$ или $O(k)$ вершин); окончательной конструкции не получено, поэтому приведена стандартная префиксная.
// 2-SAT. Переменная i: вершина 2i — «x_i истинна», 2i+1 — «x_i ложна»; отрицание = XOR с 1.
struct TwoSat {
int n;
SCC scc;
TwoSat(int n) : n(n), scc(2 * n) {}
// литерал: номер вершины (2*i или 2*i+1). Дизъюнкт (a ∨ b) = (¬a → b) ∧ (¬b → a)
void addOr(int a, int b) { scc.addEdge(a ^ 1, b); scc.addEdge(b ^ 1, a); }
static int lit(int var, bool value) { return 2 * var + (value ? 0 : 1); }
bool solve(vector<bool> &ans) {
scc.run();
ans.assign(n, false);
for (int i = 0; i < n; i++) {
if (scc.comp[2 * i] == scc.comp[2 * i + 1]) return false; // x и ¬x в одной компоненте — решения нет
// comp идёт от стоков к истокам; true получает та вершина, которая встречается в топсорте ПОЗЖЕ, то есть имеет меньший comp
ans[i] = scc.comp[2 * i] < scc.comp[2 * i + 1];
}
return true;
}
};// «Не более одной истинной среди x_0..x_{k-1}» за O(k) дизъюнктов: вводим префиксные переменные p_i = «среди x_0..x_i есть истинная».
// Переменные x_i имеют номера xv + i, префиксные — pv + i (место под них нужно выделить в TwoSat заранее).
void atMostOne(TwoSat &T, int xv, int pv, int k) {
for (int i = 0; i < k; i++) {
T.addOr(TwoSat::lit(xv + i, false), TwoSat::lit(pv + i, true)); // x_i → p_i
if (i + 1 < k) {
T.addOr(TwoSat::lit(pv + i, false), TwoSat::lit(pv + i + 1, true)); // p_i → p_{i+1}
T.addOr(TwoSat::lit(pv + i, false), TwoSat::lit(xv + i + 1, false)); // p_i → ¬x_{i+1}
}
}
}4:22:50 Реализация. Для переменной $x_i$ вершины $2i$ ($x_i$) и $2i+1$ ($\lnot x_i$); тогда отрицание любой вершины — это v ^ 1 (лайфхак из лекции).
4:24:17 Пример: микросхема. На плоскости даны точки-контакты; некоторые пары нужно соединить проводами, каждый провод — ломаная не более чем с одним поворотом на $90^\circ$, то есть для пары есть два варианта («верхний» и «нижний» уголок); провода не должны пересекаться. Для каждого провода заводим булеву переменную (какой из двух вариантов), для каждой пары проводов перебираем четыре комбинации вариантов и для пересекающихся запрещаем комбинацию дизъюнктом из двух литералов. Лектор отмечает, что это задача уровня финала ACPC (одна из лёгких); «пар проводов» $O(n^2)$. Другой пример: в вершинах графа лежат булевы переменные, и на ребро накладывается условие на пару переменных на его концах.
4:31:19 Повторение: рёберная двусвязность. Две вершины эквивалентны, если между ними есть два пути, не пересекающихся по рёбрам; классы получаются, если удалить из графа мосты.
4:33:01 Вершинная двусвязность определяется на рёбрах: два ребра эквивалентны, если между ними есть два пути, не пересекающиеся по вершинам; равносильно — они лежат на общем простом цикле. Классы эквивалентности называются блоками (компонентами вершинной двусвязности). Блоки получаются, если «разрезать» граф по точкам сочленения (сама точка принадлежит всем блокам, которые в ней сходятся).
4:40:19 Круглоквадратное дерево. Круглые вершины — вершины исходного графа (номера $1..n$), квадратные — блоки. Каждый блок соединён со всеми своими вершинами. Получается двудольное дерево (для связного графа).
4:44:39 Свойства. (1) Точка сочленения — это круглая вершина степени не меньше двух (лежит на стыке нескольких блоков). (2) Мост — блок из ровно двух вершин. (3) Любой простой путь между $a$ и $b$ в исходном графе проходит по тем же блокам, что и путь в дереве между $a$ и $b$; число точек сочленения на пути равно длине пути, делённой на два (за вычетом концов).
4:47:29 Задача (мотивация). Существует ли в графе простой путь из $a$ в $b$, проходящий через вершину $c$? Ответ: блок, содержащий $c$, должен лежать на пути от $a$ до $b$ в круглоквадратном дереве (или $c$ сама на этом пути). Такие запросы дальше решаются обычными методами для деревьев.
4:49:56 Построение — один DFS. Алгоритм совпадает с поиском точек сочленения. Храним глобальный стек вершин. При возвращении из ребёнка $c$ проверяем, не уходит ли поддерево $c$ выше $v$: если $up_c\ge tin_v$ (как в поиске точек сочленения), то все вершины, добавленные в стек за время обработки $c$, образуют блок вместе с $v$. Тогда создаём квадратную вершину, соединяем её с этими вершинами и выбрасываем их из стека; вершина $v$ остаётся в стеке (она ещё может войти в другие блоки). Если же есть ребро выше — компонента продолжается, и рано её отсекать (4:56:12).
// Круглоквадратное дерево (block-cut tree): круглые вершины 0..n-1 — вершины графа, квадратные n.. — блоки (компоненты вершинной двусвязности).
struct BlockCut {
int n, timer = 0;
vector<vector<int>> g, tree;
vector<int> tin, up, stk;
BlockCut(int n, const vector<pair<int,int>> &edges) : n(n), g(n), tin(n, -1), up(n) {
for (auto &e : edges) { g[e.first].push_back(e.second); g[e.second].push_back(e.first); }
tree.resize(n);
for (int v = 0; v < n; v++) if (tin[v] < 0) { dfs(v, -1); stk.clear(); }
}
void dfs(int v, int p) {
tin[v] = up[v] = timer++;
stk.push_back(v); // стек вершин текущего блока
for (int to : g[v]) {
if (to == p) continue; // (кратные рёбра на блоки не влияют)
if (tin[to] >= 0) { up[v] = min(up[v], tin[to]); continue; }
dfs(to, v);
up[v] = min(up[v], up[to]);
if (up[to] >= tin[v]) { // v отделяет поддерево to: вынимаем из стека целый блок
int block = tree.size(); tree.push_back({});
int x;
do { x = stk.back(); stk.pop_back(); tree[block].push_back(x); tree[x].push_back(block); } while (x != to);
tree[block].push_back(v); tree[v].push_back(block); // сама v остаётся в стеке — она в блоке, но не уходит из стека
}
}
}
};