https://contest.ucup.ac/contest/4126/problem/20250
Дан полный граф на 10^5 вершин, в нем каким-то странным неявным образом заданы стоимости ребер. Нужно найти минимальный остов.
Впервые в жизни пригодился алгоритм Борувки! Он работает следующем образом. Вначале все вершины поместим в отдельные компоненты. Пока компонент больше одной, для каждой найдем минимальное ребро в другую, а потом добавим все такие ребра. Идея в том, что всего таких итераций будет логарифм. Поэтому, если для каждой вершины уметь быстро находить ближайшую не из текущей компоненты, то итоговая сложность алгоритма получится
O(n * logn * быстро).За быстро в данном случае обозначает, что мы будет хранить дерево отрезков, где в каждом узле будем хранить два минимальных расстояния (до двух различных компонент). Тогда, чтобы найти минимальное ребро от вершины
v в другую компоненту, посмотрим на минимум на всем массиве, и возьмем тот из двух элементов, который не равен текущей компоненте.