Как восстановить рёбра остова MST в алгоритме Краскала через DSU?
Реализую Краскала с DSU: сортирую рёбра по весу и добавляю, если концы в разных компонентах. Вес MST считаю нормально, но в задаче просят ещё вывести сами рёбра остова. Как их собрать, и как понять, что граф несвязен (остов не существует)?
2 ответа
Идея Краскала: сортируем рёбра по возрастанию веса и жадно берём ребро, если оно соединяет две разные компоненты (проверка через find). Чтобы восстановить остов — просто складываем взятые рёбра в вектор; их будет ровно n-1 для связного графа.
struct Edge { int u, v, w; };
// DSU из предыдущих ответов
long long mst = 0;
vector<Edge> tree;
sort(edges.begin(), edges.end(),
[](const Edge& a, const Edge& b){ return a.w < b.w; });
DSU dsu(n);
for (const Edge& e : edges) {
if (dsu.unite(e.u, e.v)) { // соединило разные компоненты
mst += e.w;
tree.push_back(e); // ребро вошло в остов
if ((int)tree.size() == n - 1) break; // остов готов
}
}
if ((int)tree.size() != n - 1) {
// граф несвязен — остов не существует
}
Сложность: сортировка O(E log E), DSU-проход O(E·α(n)), итого O(E log E) по времени, O(V + E) памяти. Признак несвязности: после прохода взято меньше n-1 рёбер. Не забудьте long long для суммы — веса до 10^9 и V до 10^5 дают переполнение int.
Нюанс, который ломает много решений: если в задаче рёбра двунаправленные и могут быть кратные/петли, unite сам отсекёт петли (u и v уже в одной компоненте) и лишние параллельные рёбра — отдельной чистки не нужно. А вот если граф ориентированный, Краскал к MST вообще неприменим (там нужен Эдмондс/Чу-Лю-Эдмондс для минимального арборесцентного дерева) — частая ловушка в условиях, где «дерево» на самом деле про ориентированный граф.