Поиск в глубину и применения (12 декабря 2017)

1. [20 минут] Компоненты сильной связности
   1. Алгоритм поиска за O(V+E) двумя dfs (topsort + красим по обратным рёбрам)
   2. Доказательство корректности
   3. Применение: конденсация матрица достижимости за O(VE)
      
2. [20 минут] Эйлеровость
   1. Критерий эйлеровости для ор и неор
   2. Доказательство и элементарный алгоритм поиска пути:
      выделим цикл жадным циклом for (идём вглубь до упора), по индукции сделаем из каждой компоненты оставшихся рёбер Эйлеровы цикл, склеим.
   3. Алгоритм поиска для орграфа за O(V+E) одним dfs (result.push_back(e); на выходе из dfs)
   4. Картинку с примером
   5. Алгоритм поиска для неорграфа отличается тем, что после прохода по ребру нужно удалить парное пройденному.
      Удаляем лениво: Edge.rev->deleted = true;

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