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

Другой способ использовать лемму о безопасном ребре — отсортировать все ребра и пытаться добавлять их в изначально пустой остов в порядке возрастания их весов.

Если очередное ребро соединяет какие-то две уже соединенные вершины, то проигнорируем его. Иначе оно является безопасным, так как оно минимальное из соединяющих какие-то две различные компоненты, и его можно добавить.

Звучит очень просто: отсортировать все рёбра, пройтись по ним циклом и делать проверку, что вершины в разных компонентах. Но наивная проверка dfs-ом от концов всех ребер будет работать за $O(nm)$. Асимптотику можно улучшить до $O(m \log m)$ — до стоимости сортировки ребер — если для проверок использовать систему непересекающихся множеств.

За исключением реализации СНМ, код получается очень коротким:

struct Edge {
    int from, to, weight;
};

vector<Edge> edges;

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

for (auto [a, b, w] : edges) {
    // компоненты разные, если лидеры разные
    if (p(a) != p(b)) {
        // добавим ребро (a, b)
        unite(a, b);
    }
}

Раз остовные деревья являются частным случаем матроида, то алгоритм Краскала является частным случаем алгоритма Радо-Эдмондса.