Краскал: правильная реализация СНМ со сжатием путей и рангом для MST

Краскал: сортируем рёбра по возрастанию веса, идём по ним и для каждого ребра (a,b) объединяем компоненты, если a и b ещё в разных. Цикл не образуется ровно тогда, когда find(a) != find(b).

Ключ к скорости — СНМ с двумя оптимизациями. Со сжатием путей + объединением по рангу амортизированная стоимость операции = O(α(n)) (обратная функция Аккермана, практически константа).

struct DSU {
    vector<int> p, rnk;
    DSU(int n): p(n), rnk(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } // сжатие
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rnk[a] < rnk[b]) swap(a, b);
        p[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
        return true;
    }
};

long long kruskal(int n, vector<array<long long,3>> edges) { // {w,a,b}
    sort(edges.begin(), edges.end());
    DSU d(n);
    long long cost = 0; int cnt = 0;
    for (auto& [w, a, b] : edges)
        if (d.unite(a, b)) { cost += w; if (++cnt == n - 1) break; }
    return cost;
}

Сложность: O(E log E) на сортировку (доминирует) плюс O(E·α(V)) на операции СНМ. Память O(V+E).

Грабля: суммарный вес копите в long long — при E до 2·10^5 рёбер и весах до 10^9 сумма легко переполняет int.