Задачник Базовый курс EN

Что решает

связность

Статьи

DS Структура данных Система непересекающихся множеств Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма. O(α(n)) 2 задачи GRA Алгоритм Поиск в глубину Идёт вглубь, отмечает вход и выход каждой вершины и по ним находит циклы за O(V + E). O(V + E) 2 задачи GRA Алгоритм Компоненты сильной связности Группы вершин, где из любой можно дойти до любой: Тарьян за один обход, Косараю за два, O(V + E). O(V + E) 2 задачи GRA Алгоритм 2-SAT Условия «a или b»: граф следствий, компоненты сильной связности и ответ за O(n + m); на настоящих нотах. O(n + m) 1 задача GRA Алгоритм Мосты и точки сочленения Улицы и перекрёстки, без которых граф распадается: один поиск в глубину с числами tin и low, O(V + E). O(V + E) 2 задачи GRA Алгоритм Максимальный поток Наибольший поток из истока в сток и узкое место сети: Форд — Фалкерсон, Эдмондс — Карп, теорема о разрезе. O(V E²) 2 задачи GRA Алгоритм Алгоритм Диница Наибольший поток фазами: слоистая сеть, блокирующий поток, указатели; O(V²E), а в единичных сетях O(E√V). O(V² E) 2 задачи GRA Алгоритм Минимальный разрез Самая дешёвая граница в графе: вырезает предмет на фотографии и находит слабое место сети. O(m n² |C|) 2 задачи

Задачи

Ночные перекрытия Тёмные острова Цикл импортов Гнёзда кукушки Две руки Две ячейки Маршруты без общих перекрёстков Недостающие улицы Перекрытия улиц Перекрёсток на ремонте Слабое место сети Запасной маршрут Кратчайшие маршруты без общих пересадок Подписи сёл на карте

Часто рядом

классика 8 граф 7 олимпиады 5 карты и навигация 4 обход 3 стек 3 собеседования 3 сети 3 потоки 3 изображения 2 выполнимость 2 взвешенный граф 2