На чём держится
система непересекающихся множеств
Статьи
DS
Структура данных
Система непересекающихся множеств
Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма.
O(α(n))
2 задачи
GRA
Алгоритм
Минимальное остовное дерево
Самая дешёвая сеть, связывающая все вершины: Борувка, Краскал и Прим — три способа применить одну лемму.
O(E log V)
2 задачи
GRA
Алгоритм
Наименьший общий предок
Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн.
O(log n) на запрос
2 задачи
Задачи
Часто рядом
классика 3 дерево 2 офлайн-запросы 2 наука и физика 2 граф 2 связность 1 массив 1 амортизация 1 карты и навигация 1 изображения 1 остовное дерево 1 жадность 1