Алгоритмы и структуры данных 4. Графы, алгоритм DFS, компоненты сильной связности

Таймкоды: 00:00:00 - Интро 00:00:05 - Графы 00:04:00 - Алгоритм dfs (depth-first search) - поиск в глубину 00:13:52 - Лемма о белых путях 00:25:45 - Следствие 1 (про достижимые из S вершинах) 00:27:45 - Следствие 2 (про обнаружение циклов) 00:38:05 - DAG (directed acyclic graph) - ориентированный граф без циклов 00:40:00 - Топологическая сортировка графа 00:41:07 - Утверждение (про существование топ. сорт.) 00:53:33 - Сильная связность 00:55:07 - Компоненты сильной связности (КСС) 00:58:13 - Задача (выделение КСС - алгоритм Косарайю) 01:17:31 - Задача (2SAT) Дата лекции: 24.02.26 Лектор: Степанов Илья Данилович Оператор: Пахомов Михаил Монтажер: Пахомов Михаил Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvZcovb3rsD3_g1fIQIAOZVg Плейлист в ВК: https://vkvideo.ru/playlist/-206078025_234