------> Топсорт

[1] определение: для всех ребер (v, u) u позже v

[3] dfs(int v) {
      if (u[v]) 
        cycled |= (u[v] == 1);
        return
      u[v] = 1
      for (int u : g[v]) dfs(u)
      u[v] = 2
      topsort.push_front(v)
    }

[5] корректность: рассмотрим (v, u), в какой-то момент запустились из v
    если u черная, уже добавлена
    если белая, запустимся от нее, она закончится и добавится раньше (в сорте после)
    если серая, цикл смерть

[10] второй алгоритм
     вершину, в которую нет входящих ребер, можно поставить в начало
     ребра из нее теперь всегда корректны, удалим их, получили граф без одной вершины
     такая вершина была: если нет, можно либо бесконечно идти назад по обратным ребрам, либо зациклиться
     отсюда уже очевиден v^2, но простое наблюдение: обнулиться может только степень вершин, у которых только что ушло ребро
     while (!q.empty()) // q -- вершины степени 0
       int v = q.pop_front()
       topsort.push_back(v)
       for (int u : g[v])
         if (--in_deg[u] == 0)
           q.push_back(u)

[10] динамика по топсорту на примере кузнечика по графу
     можно делать динамикой по топсорту
     пример, как делать вперёд:
     for (int v : topsort)
       for (int u : g[v])
         count[v] += count[u]
     если сделать ленивую динмику, то явный топсорт не нужен, просто дфс
     int dfs(int v)
       if (count[v] != -1) return count[v]
       count[v] = is_end[v]
       for (int u : g[v]) count[v] += dfs(u)
       return count[v]

[20 минут] ксс
  напоминание: u, v сильно связны, если u достижима из v и v достижима из u
  это отношение эквивалентности, классы эквивалентности этого отношения -- компоненты сильной свзяности
  имными словами, ксс -- множество вершин, максимальное по включению, где каждая вершина достижима из каждой
  конденсация графа G -- граф H, вершины которого -- ксс графа G,
    ребро между двумя вершинами есть, если есть ребро между соотв. ксс
  алгоритм сильной связности за O(VE)
  алгоритм сильной связности за O(E)

---- Перерыв! ----

[20 минут] ксс
  доказательство корректности

[20 минут] эйлеровость
  [5 минут] Повторение
    Определение (цикл, путь)
    Критерий эйлеровости для ор и неор
    Алгоритм поиска пути тупой: выделим цикл жадным циклом for (идём вглубь до упора), по индукции сделаем из остатка Эйлеров цикл, склеим.
  -- пауза --
  Алгоритм поиска для орграфа за O(V+E):
  vector<Edge> result, c[N];
  void dfs( int v ) {
    while (edges[v].size()) {
      Edge e = edges[v].back(); edges[v].pop_back()
      dfs(e.to);
      result.push_back(e);
    }
  }
  !!! Картинку с примером
  Алгоритм поиска для неорграфа отличается тем, что после прохода по ребру нужно удалить его парное, идущее обратно
  Удаляем лениво: Edge.rev->deleted = true;