Параллель B: различия между версиями
Материал из Algocode wiki
Debnatkh (обсуждение | вклад) |
Debnatkh (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
# DFS: время входа-выхода и топсорт. | # DFS: время входа-выхода и топсорт. | ||
# Проверка на двудольность. | # Проверка на двудольность. | ||
| − | # DFS: конденсация. | + | # [[Конденсация графа|DFS: конденсация]]. |
| − | # 2-SAT. | + | # [[2-SAT]]. |
| − | # Мосты и точки сочленения. | + | # [[Поиск мостов|Мосты]] и [[Поиск точек сочленения|точки сочленения]]. |
# Эйлеровы пути и циклы. | # Эйлеровы пути и циклы. | ||
Версия 16:30, 15 сентября 2019
1. Обход в глубину и его применения (14 сентября)
- Базовый DFS. Примеры:
- Проверка графа на связность.
- Выделение всех компонент связности.
- DFS: время входа-выхода и топсорт.
- Проверка на двудольность.
- DFS: конденсация.
- 2-SAT.
- Мосты и точки сочленения.
- Эйлеровы пути и циклы.