dfs (13 ноября 2013)

1. Повторим хранение графа
1. int count[N][N], weight[N][N]
2. vector c[N], w[N]
3. int head[N]; edge e[E];
2. Пути (совсем простая часть)
1. Путь из v в a
2. Путь из v в A
3. Путь из A в v
3. Рекурсия (учимся жить без стека)
1. Stack: замеряем память [код]
2. Изучаем настройки компилятора/операционной системе (python, java, c++)
3. Учимся обходиться без stack-а: dfs, который ищет путь, на stack, на queue
4. Полноценный dfs без использования стандартного стека.
4. Двусвязность и сильная связность (на это уйдет много времени) [код]
1. Ориентированный граф, сильная связность, ориентация графа
2. Компоненты реберной двусвязности и мосты [код]
3. Компоненты вершинной двусвязности и точки сочленения
4. Тестирование мостов [slow] [gen] [cmd]
5. Классные задачки на dfs
1. Покраска графа в два цвета
2. Разбиение графа на две клики
3. У каждой вершины 3 врага, разбить на две доли так, чтобы у каждой вершины в ее доли было не более 1 врага
4. Покраска дверей: каждое ребро дверь, с одной стороны красная, с другой зеленая. Нужно, чтобы в каждой вершине разница была не больше 1.
5. Ориентация графа: нужно ориентировать граф так, чтобы максимальная исходящая степень была минимальна