1. Компоненты сильной связности 1.1 Напоминание про алгоритм за O(k * dfs) 1.2 Лемма о ребре между компонентами СС и временах выхода. 1.3 Получаем алгоритм за O(Vа+E) двумя dfs (topsort + красим по обратным рёбрам) 1.4 Конденсация, определение. 2. Эйлеровость 2.1 Определение эйлерова цикла 2.1 Вместе формулируем предикат эйлеровости, ор. и неор. случай. (!) В ор. случае достаточно слабой связности. 2.2 Элементарный алгоритм поиска пути: идём вперёд, находим любой цикл, приклеиваем остатки. 2.3 алгоритм для ор 2.4 отличие для неор. 3. Двусвязность. 3.1 Def: рёберная двусвязность, доказательство транзитивности. 3.2 Def: мост. Понимаем что рёберно двусвязно если не через мост. Ищем мосты за O(VE) 3.3 Динамика up[v], пишем код, учимся искать мосты 3.4 Стек вершин, строим сами компоненты 3.5 Def: вершинная двусвязность, доказательство. 3.6 Точки сочленения, ищем за O(VE). Предикат точек сочленения. 3.7 Модифицируем алгоритм чтобы искать компоненты двусвязности. 4. 2SAT 4.1 Определение. Переформулировка через импликации, сведение в обе стороны. 4.2 Решаем в форме импликаций, граф из 2n вершин. 4.3 Налюдение про достижимость x->not(x). Видим критерий неразрешимости в компонентах сильной связности. 4.4 Решение за O(V+E): рассматриваем компоненты снизу вверх. 4.5 Доказываем корректность, 4 неравенства