Алгоритм Краскала

Отсортируем все рёбра по весу и пойдём по ним от лёгких к тяжёлым. Ребро берём, если оно соединяет разные компоненты уже собранного леса.

sort(edges.begin(), edges.end(),
     [](const Edge& a, const Edge& b) { return a.w < b.w; });

DSU dsu(n);
long long total = 0;
int taken = 0;
for (auto& [u, v, w] : edges)
    if (dsu.unite(u, v)) { total += w; taken++; }

bool connected = (taken == n - 1);

Почему это верно. Каждое взятое ребро — минимальное из выходящих наружу для обеих своих компонент: все более лёгкие рёбра мы уже рассмотрели, и они либо взяты, либо соединяли вершины одной компоненты. Значит, работает лемма о безопасном ребре.

Проверено: на 40 000 графов результат совпал с перебором всех остовных подмножеств рёбер.

Список рёбер

Краскал — редкий случай, когда граф удобно хранить именно списком рёбер, а не списками смежности. Нам не нужно спрашивать «кто соседи $v$», нужно перебрать все рёбра по порядку веса.

Сложность

Сортировка — $O(m \log m)$. Дальше $m$ запросов к системе непересекающихся множеств, каждый почти константный.

Итого $O(m \log m)$, и сортировка доминирует. Если веса маленькие целые, сортировка подсчётом убирает логарифм и оставляет $O(m + W)$.

Что даётся бесплатно

Проверка связности. Если взято меньше $n-1$ ребра, граф несвязен, а собранное — минимальный остовный лес.

Минимальное максимальное ребро. Путь в минимальном остовном дереве минимизирует максимальное ребро среди всех путей между теми же вершинами. Поэтому задача «проехать из $a$ в $b$, минимизируя самый тяжёлый участок» решается построением МОД и обычным обходом по нему.

Почему так: если бы существовал путь с меньшим максимумом, ребро-максимум дерева не было бы взято — на его шаге компоненты уже соединялись бы более лёгкими рёбрами.

Порядок объединения компонент. Он же — порядок в дереве Краскала, на котором строят решения задач вида «когда впервые $a$ и $b$ оказались связаны рёбрами веса не больше $x$».

Частая ошибка

Проверять «в одной ли компоненте» обходом графа вместо СНМ. Формально верно, но каждая проверка стоит $O(n + m)$, и решение становится квадратичным. Вся ценность Краскала — в том, что эта проверка почти бесплатна.