Поиск в глубину: двусвязность, 2-sat (22 января 2021)

1. Разбираем код и dfs-ы
   1. Проверка внутри или снаружи
   2. Цикл for
   3. Инкапсуляция через struct
   4. Константы
   
   
2. [6 минут] Раскраски
   1. В 2 цвета = dfs
   2. В 3 цвета = трудно (умеют только за экспоненту). В минимальное число цветов, тем более.
   3. Но как всё-таки действовать? жадный алгоритм за O(V+E) через удаление вершины минимальной степени
   
   
3. [30 минут] Двусвязность
   1. Определения: рёберная, вершинная, мосты, точки сочленения
   2. Наивный алгоритм поиска всех мостов и точек сочленения за O(VE)
   3. Поиск компонент по данным мостам, точкам сочленения. Упор на то, что компоненты вершинной двусвязности − множества рёбер.
   4. Идея алгоритма поиска мостов: если пройдём вниз по мосту, вверх подняться без этого моста не сможем
   5. Алгоритм поиск мостов через 1 dfs.
   6. Учим этот dfs искать компоненты (доставать их из стека).
   7. Таким же образом ищем точки сочленения
   8. Таким же образом ищем компоненты вершинной двусвязности (стек рёбер, что делать с парным ребром)
   9. Корректность всех алгоритмов (на самом деле алгоритм един, его конечная версия ищет всё и сразу)
   10. Условия: (mt[x] ≥ t[v]) ⇔ is_bridge (new_component), (mt[x] ≥ t[v]) ⇔ is_point (new_component)
   
   
4. [15 минут] 2-SAT
   1. Определение. Отличие SAT и 2-SAT.
   2. Примеры: подписи к отрезкам.
   3. Орграф импликаций на 2n вершинах.
   4. Противоречия. Жадное решение: попробуем x₁ = true, если пришли к противоречию, значит x₁ = false. O(VE).
   5. Видим в графе импликаций компоненты сильной связности. Решение за O(V+E): рассматриваем компоненты снизу вверх.
   6. Корректность: x=e ⇒ не появится противоречий

1. Если успеем − алгоритм Полларда