Поиск в глубину: сильная связность, эйлеровость (15 января 2021)

1. Хранение графа
   1. Если удалять рёбра? vector<set<int>>
   2. Если плотный граф V = 10 000? vector<bitset>
   3. Если хотим минимизировать память? sizeof(vector<int>) = 24, мультисписок
2. Кодим dfs
   1. Восстановление пути на обратном ходу рекурсии
   2. Инкапсуляция графа, struct
   3. Локальный функции, function
   4. Рёбра − list initialization
   
   
3. [20 минут] Компоненты сильной связности
   1. Тривиальный алгоритм поиска за O(kE)
   2. Алгоритм поиска за O(V+E) двумя dfs (topsort + красим по обратным рёбрам)
   3. Доказательство корректности (любая достижимая по обратным рёбрам другая компонента уже покрашена)
   4. Конденсация сс. Определение, построение.
   
   
4. [20 минут] Эйлеровость
   1. Критерий эйлеровости для ор и неор
   2. Доказательство и элементарный алгоритм поиска пути:
      выделим цикл жадным циклом for (идём вглубь до упора), по индукции сделаем из каждой компоненты оставшихся рёбер Эйлеровы цикл, склеим.
   3. Алгоритм поиска для орграфа за O(V+E) одним dfs (result.push_back(e); на выходе из dfs)
   4. Алгоритм поиска для неорграфа отличается тем, что после прохода по ребру нужно удалить парное пройденному.
      Удаляем лениво: isdeleted[edge.index] = true;
   5. Картинки с примерами (почему важен цикл while, почему важно удалять ребро)