Почему мой Краскал на DSU выдаёт WA на кратных рёбрах и петлях — где ошибка?
Реализовал Краскал, на простых тестах остов верный, но на графе с петлёй (ребро u-u) и кратными рёбрами между одной парой ловлю WA по весу MST. Вот ядро:
for (auto& e : edges) {
int a = dsu.find(e.u), b = dsu.find(e.v);
mst += e.w; // ???
dsu.unite(e.u, e.v);
}
Что я делаю не так?
2 ответа
Баг в том, что вы прибавляете вес каждого ребра, не проверяя, соединило ли оно разные компоненты. Петля (u==u) и второе из кратных рёбер не должны входить в остов, но mst += e.w добавляет их всё равно. Прибавлять вес нужно только при успешном unite:
sort(edges.begin(), edges.end(),
[](auto& a, auto& b){ return a.w < b.w; });
long long mst = 0; int taken = 0;
for (auto& e : edges) {
if (dsu.unite(e.u, e.v)) { // true только если разные компоненты
mst += e.w;
++taken;
}
}
if (taken != n - 1) { /* несвязный граф */ }
Петля: unite(u,u) вернёт false (одна компонента) — вес не добавится, верно. Кратные рёбра: первое (самое лёгкое после сортировки) соединит компоненты и войдёт, остальные дадут false и отсеются. Заодно вы, похоже, забыли отсортировать рёбра по весу — без этого Краскал вообще неверен. Сложность корректной версии — O(E log E). И long long для суммы, чтобы веса не переполнили int.
Ещё одна тонкость, всплывающая на петлях: если граф гарантированно связен, можно сразу break после taken == n-1, не дочитывая остальные рёбра — мелкая, но иногда нужная оптимизация под TL. И проверьте индексацию вершин: если вход 1-индексирован, а DSU создан на [0..n-1], то find(n) вылезет за вектор (UB), что на петлях/кратных как раз и может «случайно» проявиться как WA вместо честного RE.