Поиск в глубину (29 октября 2015, Серёжа)

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