Минимальные остовные деревья. Алгоритмы Краскала и Прима. Системы непересекающихся множеств.

Остовы минимального веса. Лемма о минимальном ребре в разрезе. Алгоритмы Краскала и Прима. Структура DSU (disjoint set union) Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства). Подробнее о поступлении в Школу анализа данных от Академии Яндекса: