Графы

0. Про реверс битовый
0.1 За 2^n n, 2^n через перебор, 2^n через дп

1. Графы, G=(V,E)
1.1 Глоссарий терминов: vertex, edge, arc, deg, directed/undirected, weighted/unweighted
1.2 loop, path, cycle, simple graph/multigraph, indeg, outdeg
1.3 Отношение достижимости
1.4 Связность в неорграфе это отношение эквивалентности
1.5 Четыре способа хранения рёбер (список, матрица см, список см, мультисписок)

2. Поиск в глубину
2.1 Из одной вершины; из всех вершин
2.2 Размечаем компоненты связности
2.3 Ищем путь
2.4 Проверяем двудольность
2.5 Классификация рёбер (4 типа), классификация рёбер в неориентированном графе
2.6 Цикл в неорграфе, в орграфе (три цвета в dfs)
2.7 Формально доказываем, что (1) dfs(v) посещает всё достижимое из v
2.8 (2) алгоритм из 2.6 для орграфа справится

3. Больше поиска в глубину
3.1 Топсортим граф, tin, tout, лемма про tout для ребра
3.2 Алгоритм для топсортировки без dfs
3.3 Сильная связность, отношение эквивалентности
3.4 Очень простой алгоритм за O(VE).