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

1. Замечания к прошлым задачам [code]
1. Частичные суммы: не нужен IF.
2. Битовые сдвиги (знаковые и нет, С++ и java)
3. Разбор задачи permutations2: отложенные операции, решение за Nsqrt(NlogN)
2. Кодим dfs
1. Компоненты связности [code]
2. Топологическая сортировка [code]
3. Покраска в два цвета [code]
4. Выделение мостов и компонент реберной двусвязности [code]
5. Эйлеров цикл (в ориентированном графе, комментарий к неориентированному графу) [code]
6. Хранение графа: массив векторов или мультисписок на массиве. [code]
7. Еще кодим. Замеряем, сколько памяти используется при рекурсии. [code]
3. Задачи на dfs
1. Ориентация графа.
2. Известно, что граф можно разделить на две клики. Сделать это за O(E).
3. Найти путь из множества вершин A в множество вершин B.
4. Дополнение графа до Эйлерова
5. У каждой вершины не более 3 врагов. Разбить на 2 доли так, чтобы с вершиной в долю попало не более 1 врага.
6. 2-SAT. Каждую вершину покрасить в один из двух цветов так, чтобы соседние вершины были покрашены в различные цвета.
7. HARD: дополнение графа до сильносвязного.