Параллель B

Страница параллели

1. Обход в глубину и его применения (14 сентября)

1. Базовый DFS. Примеры:
   1. Проверка графа на связность.
   2. Выделение всех компонент связности.
2. DFS: время входа-выхода и топсорт.
3. Проверка на двудольность.
4. DFS: конденсация.
5. 2-SAT.
6. Мосты и точки сочленения.
7. Эйлеровы пути и циклы.