31.10 bfs. Двудольность. Запросы в дереве: является ли предком, число детей k поколения, LA offline.

Обход в ширину через выписывание слоев. Упрощенная реализация с помощью очереди. Дерево bfs, его свойства для ориентированного и неориентированного графа. Алгоритм раскраски графа в 2 цвета с помощью dfs. Критерий двудольности, его доказательство. Вид дерева bfs двудольного графа. dfs на дереве без массива used. Понятие эйлерова обхода, связь с временем входа и выхода. Использование для быстрого ответа на запросы является ли одна вершина предком другой и о числе потомков вершины в k поколении. Level ancestor offline за O(n + q).