dfs (29 октября)

1. Хранение графа (матрица смежности, список рёбер)
2. Собственно dfs (алгоритм, время работы, поиск компонент связности)
3. Классификация рёбер для ориентированного графа: прямые, обратные, перекрёстные
4. Классификация рёбер для неориентированного графа: прямые, обратные (нет перекрёстных!)
5. Топологическая сортировка. Определение, алгоритм за время O(V+E).
6. Покраска в два цвета
7. Алгоритм поиска цикла в ориентированном графе (бело-серо-чёрный dfs)
8. Сильная связность: определение, наивный алгоритм за O(VE)
9. Сильная связность: алгоритм за O(V+E)

dfs (5 ноября)

1. Сильная связность: конденсация графа за O(V+E).
2. Поиск мостов и компонент рёберной двухсвязности за O(V+E)
3. Поиск точек сочленения и компонент вершинной двухсвязности за O(V+E)
4. Эйлеров путь, цикл: критерий эйлеровости, алгоритм поиска за O(V+E)
5. 2-SAT, решение за O(V+E)