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

Что решает

обход

Статьи

GRA Алгоритм Поиск в ширину Обходит граф слоями и находит пути с наименьшим числом рёбер за O(V + E). O(V + E) 2 задачи GRA Алгоритм Поиск в глубину Идёт вглубь, отмечает вход и выход каждой вершины и по ним находит циклы за O(V + E). O(V + E) 2 задачи GRA Алгоритм Компоненты сильной связности Группы вершин, где из любой можно дойти до любой: Тарьян за один обход, Косараю за два, O(V + E). O(V + E) 2 задачи GRA Алгоритм Мосты и точки сочленения Улицы и перекрёстки, без которых граф распадается: один поиск в глубину с числами tin и low, O(V + E). O(V + E) 2 задачи GRA Алгоритм Эйлеров путь Пройти каждое ребро ровно раз: правило нечётных вершин и алгоритм Хирхольцера за O(E). O(V + E) 3 задачи DP Приём Динамика на деревьях Ответ поддерева — из ответов детей: проход от листьев к корню, а для всех корней сразу — перерасчёт с корня. O(n) 2 задачи

Задачи

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

Часто рядом

классика 6 граф 5 олимпиады 5 собеседования 4 стек 4 связность 3 карты и навигация 3 рекурсия 2 компиляторы 2 динамика 2 биоинформатика 2 кратчайший путь 1