Поиск в глубину 2 (?? января 2024)

1. Разбираем код dfs-а
   1. Инкапсуляция графа, struct
   2. Локальные функции, function
   3. Рёбра − list initialization
   4. Проверка внутри или снаружи
   5. Цикл for
   6. Инкапсуляция через struct
   7. Константы
   
   
2. [6 минут] Раскраски
   1. Покраска в 2 цвета.
   2. В 3 цвета = трудно (умеют только за экспоненту). В минимальное число цветов, тем более.
   3. Но как всё-таки действовать? жадный алгоритм за O(V+E) через удаление вершины минимальной степени
   
   
3. [20 минут] Эйлеровость
   1. Критерий эйлеровости для ор и неор
   2. Доказательство и элементарный алгоритм поиска пути:
      выделим цикл жадным циклом for (идём вглубь до упора), по индукции сделаем из каждой компоненты оставшихся рёбер Эйлеровы цикл, склеим.
   3. Алгоритм поиска для орграфа за O(V+E) одним dfs (result.push_back(e); на выходе из dfs)
   4. Алгоритм поиска для неорграфа отличается тем, что после прохода по ребру нужно удалить парное пройденному.
      Удаляем лениво: is_deleted[edge.index] = true;
   5. Картинки с примерами (почему важен цикл while, почему важно удалять ребро)