Минимальное остовное дерево (MST): Алгоритмы Крускала и Прима

Лемма о безопасном ребре

Пусть $G = (V, E, w)$ — связный взвешенный граф, $A \subset E$ — подмножество ребер, входящих в некоторый MST. Разрез $(S, V - S)$ графа $G$ согласован с $A$, если ни одно ребро из $A$ не пересекает разрез.

Лемма: Если ребро $(u, v)$ является легким ребром (имеет минимальный вес среди всех ребер, пересекающих разрез), то оно является безопасным для добавления к $A$.

// Алгоритм Крускала
struct Edge { int u, v, w; };

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a.w < b.w; });
    DSU dsu(n);
    int mstWeight = 0;
    for (const auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mstWeight += e.w;
        }
    }
    return mstWeight;
}