Задачи, которые рассказать в начале лекции
  1. Разбить кактус на циклы
  2. Написать на бумажке код dfs-а без системного стека — на своём стеке.
  3. Проверить наличие пути в орграфе и неорграфе за O(log^2n) памяти
-----------

какие бывают графы: ор/неор, мульти (с кратными ребрами и петлями), (взвешенные)
основные понятия
  путь, [реберно-]простой путь, цикл, простой цикл, контур
  отношения достижимости, связности, сильной и слабой связности, компоненты связности
  [входящая и выходящая] степень вершины
хранение графа в C++
  struct edge { int from, to; }; edge a = {2, 3};
  матрица смежности: bool[][], vector<bool>[] или bitset<>[], int[][] для мульти или взвешенного, egde[][]
    -: перебор соседей O(n), память O(n^2)
    +: наличие/добавление/удаление ребра за O(1)
    отдельно про bitset<N>. Размер задается константой, в compile-time. В runtime можно vector<bool>.
      можно работать как с массивом + побитовые операции (у vector<bool> нет) и красивый io
      O(n), но маленькая константа, можно считать n/32 (unsigned long в gcc, ull в ms, иногда n/64, но лучше на это не рассчитывать)
  vector/set<int/edge>[]
    +: перебор соседей O(deg), память O(m)
    -: наличие/удаление ребра за O(deg), но можно [unordered_]set, хотя и [еще реже]редко, ибо сильно портит константу времени и памяти
  мультисписок
    add_edge(u, v, ...) { value[cnt] = edge(u, v, ...); next[cnt] = head[u]; head[u] = cnt; cnt++; }
    vector быстрее перебирает соседей, ибо кеш, нет хождения по указателям
    но проигрывает мультисписку двухкратным оверхедом по памяти, долгим заполнением графа ребрами (привести данные эксперимента???)
    первое лечится reserve(deg[i])
    второе лечится подменой аллокатора
  итоговая мораль: в разных задачах все по-разному, но чаще всего хватает vector<>[], на худой конец с быстрым аллокатором

dfs(int v) // простейшая версия
  if (visited[v]) return
  visited[v] = true
  for (int u : g[v]) dfs(u)
for (int i = 1; i <= n; ++i) if (!visited[i]) dfs(i)

путь между двумя вершинами
  bool dfs(int v) // bool! часто удобно
    if (visited[v]) return false
    visited[v] = true
    for (int u : g[v])
      if (u == end || dfs(u))
        ans.push_front(u) // без восстановления -- выкинуть только эту строку
        return true
  dfs(start)
компоненты связности
  dfs(int v, int c)
    if (visited[v]) return
    color[v] = c
    ...
  for (int i = 1; i <= n; ++i) if (!visited[i]) dfs(i, current++)

три состояния вершины: не начался запуск (белая), начался и не кончился (серая), кончился (черная)
лемма. при запуске dfs от v, после его завершения будут помечены все вершины, достижимые из v по белым путям. и только они
  утверждение1. ни в какой момент дфса не бывает ребра между из черной в белую (но не наоборот, а внеорграфе направление неважно)
  если что-то достижимое непомечено, то на пути к ней есть ребро из черной в белую
  только они -- индукция по глубине dfs
время работы O(V + E): сумма форов в дфсе равна E, число запусков dfs равно V
замечание: один запуск работает за O(E), это видно из структуры дерева dfs
dfs строит корневое дерево (вернее, лес): у каждой вершины один предок
  древесные, прямые, обратные, перекрестные
  в неорграфе нет перекрестных, прямые=обратные

двудольность
  первую вершину можно красить в любой цвет, пусть 1
  если что-то покрашено, ясно, как красить соседей
  bool dfs(int v, int c)
    if (color[v] != 0) return color[v] == c
    color[v] = c
    for (int u : g[v]) if (!dfs(v, 3 - c)) return false
поиск цикла
  для неор: видим ребро в помеченную -- нашли цикл
    тонкость -- нужно помнить, откуда пришли (массив предков или параметр dfs)
    для мультиграфа -- номер ребра
  для ор всё хитрее, пример, где втупую найдется неорцикл
    будем хранить состояния (белая, серая, черная) явно
    bool dfs(int v)
      state[v] = 1
      for (int u : g[v]) if (state[u] == 1 || (state[u] == 0 && dfs(u))) return true
      state[v] = 2
      return false
   восстановление: либо храним стек серых вершин (ребер), либо массив предков (ребер)
   утверждение1 (напоминание). ни в какой момент дфса не бывает ребра между из черной в белую (но не наоборот, а внеорграфе направление неважно)
   утверждение2. серые вершины образуют путь, кончающийся в вершине, в которой находится дфс в текущий момент
   если нашли ребро в серую, то по утв2 нашли цикл
   если в помеченную в неор, то по утв1 она серая
   если есть цикл, есть первая вершина из него v, где побывает дфс, и есть ребро (u, v) на цикле, u достижима из v, по лемме все ок