Поиск в глубину (28 октября 2016)

  1. [15 минут] Кодим dfs
    1. Компоненты связности [code]
    2. Топологическая сортировка [code]
    3. Покраска в два цвета [code]
    4. Путь между двумя вершинами в графе [code]
  2. [15 минут] Мультисписок, banchmark
    1. Мультисписок для хранения графа [code]
    2. Сравнение мультисписка и массива векторов
    3. Замеряем, сколько памяти используется при рекурсии. [code]
  3. [30 минут] Задачи на dfs
    1. Дан ацикличный орграф, найти в нем гамильтонов путь за O(V+E)
    2. Дан ацикличный орграф, найти в нем самый длинный путь за O(V+E) [code]
    3. Найти цикл в неор графе (на лекции дан только орграф!)
    4. Найти цикл, проходящий через данное ребро графа
    5. Ориентация графа (ориентировать граф так, чтобы не было циклов)
  4. [30 минут] Более сложные задачи
    1. Известно, что граф можно разделить на две клики. Сделать это за O(E)
    2. Дан граф, построить матрицу достижимости N, M ≤ 105
    3. Есть комнаты и двери между комнатами. Нужно каждую дверь покрасить с одной стороны в зеленый цвет, с другой в оранжевый цвет так, чтобы для каждой комнаты количества зеленых и оранжевых дверей отличались не более чем на один. O(V+E).
    4. Разбить множество вершин на две доли так, чтобы у каждой вершины был сосед в другой доли. O(V+E)