3.4 — задача из примера в теме 3.2.3 «Минимальное остовное дерево»3.4 — a problem from the example in topic 3.2.3 "Minimum spanning tree"
В 3.2.3 упоминалось: сеть, соединяющая N зданий минимальной суммарной длиной кабеля, — это MST. Здесь — конкретные здания с расстояниями между ними, для которых нужно и посчитать минимальную стоимость прокладки, и явно построить сам список выбранных кабелей через алгоритм Крускала с DSU.3.2.3 mentioned that a network connecting N buildings with minimum total cable length is an MST. Here are concrete buildings with distances between them, for which both the minimum laying cost and the explicit list of chosen cables must be computed via Kruskal's algorithm with DSU.
Дано n зданий кампуса (пронумерованы 0..n-1) и список возможных прокладок кабеля `cables[i] = [a, b, cost]` — кабель между зданиями a и b стоимостью `cost`. Нужно связать все здания в единую сеть (от любого до любого можно добраться по кабелям, прямо или через другие здания) с минимальной суммарной стоимостью, и вернуть как саму минимальную стоимость, так и список выбранных кабелей.Given n campus buildings (numbered 0..n-1) and a list of possible cable layings `cables[i] = [a, b, cost]` — a cable between buildings a and b costing `cost`. Connect all buildings into a single network (any building reachable from any other, directly or through others) at minimum total cost, and return both the minimum cost itself and the list of chosen cables.
// Example
n = 4
cables = [[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,3]]
// output: cost=6, cables=[[0,1,1],[1,2,2],[2,3,3]]Прямое применение определения из 3.2.3: n=4 зданий → остовное дерево должно содержать ровно n-1=3 кабеля. Стратегия Крускала — отсортировать все кабели по стоимости по возрастанию и добавлять каждый, если он не создаёт цикл с уже добавленными (то есть соединяет две ещё не связанные части сети).Direct application of the definition from 3.2.3: n=4 buildings → the spanning tree must contain exactly n-1=3 cables. Kruskal's strategy: sort all cables by cost ascending, and add each one if it doesn't create a cycle with what's already added (i.e., it connects two parts of the network not yet linked).
кабели (0,2,4) и (1,3,5) отброшены DSU — обе пары уже связаны более дешёвыми рёбрамиcables (0,2,4) and (1,3,5) are rejected by DSU — both pairs are already connected via cheaper edges
Проверка "уже связаны" — это ровно DSU из 3.2.3, а не отдельный обход графа на каждом шаге: `find(0)` и `find(2)` после добавления первых трёх кабелей возвращают одного и того же представителя компоненты, потому что 0 и 2 уже соединены цепочкой 0-1-2 — значит кабель (0,2,4) создал бы цикл и корректно отбрасывается без обхода всего графа заново.The "already connected" check is exactly the DSU from 3.2.3, not a separate graph traversal at every step: `find(0)` and `find(2)`, after the first three cables are added, return the same component representative, because 0 and 2 are already linked via the chain 0-1-2 — meaning cable (0,2,4) would create a cycle and is correctly rejected without re-traversing the whole graph.
struct DSU {
std::vector<int> parent, rank_;
DSU(int n) : parent(n), rank_(n, 0) { std::iota(parent.begin(), parent.end(), 0); }
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (rank_[a] < rank_[b]) std::swap(a, b);
parent[b] = a;
if (rank_[a] == rank_[b]) rank_[a]++;
return true;
}
};
class Solution {
public:
std::pair<int, std::vector<std::array<int,3>>>
minCableNetwork(int n, std::vector<std::array<int,3>> cables) {
std::sort(cables.begin(), cables.end(),
[](auto& a, auto& b) { return a[2] < b[2]; }); // сортировка по cost// sort by cost
DSU dsu(n);
int totalCost = 0;
std::vector<std::array<int,3>> chosen;
for (auto& c : cables) {
if (dsu.unite(c[0], c[1])) { // не создаёт цикл — берём// no cycle created — take it
totalCost += c[2];
chosen.push_back(c);
if (chosen.size() == (size_t)(n - 1)) break; // дерево готово// the tree is complete
}
}
return {totalCost, chosen};
}
};Сложность O(E log E) — сортировка кабелей доминирует над почти константными по времени операциями DSU (O(E · α(V)), см. 3.2.3). Ранний выход `if (chosen.size() == n - 1) break;` — не обязательная, но естественная оптимизация: как только собрано n-1 рёбер, дерево уже построено, и дальнейшие кабели гарантированно создадут цикл.Complexity is O(E log E) — sorting the cables dominates the DSU operations' near-constant time (O(E · α(V)), see 3.2.3). The early exit `if (chosen.size() == n - 1) break;` isn't mandatory but a natural optimization: once n-1 edges are collected, the tree is already built, and any further cable is guaranteed to create a cycle.
Если после обработки всех кабелей `chosen.size() < n - 1`, значит исходный граф изначально был несвязным (какие-то здания невозможно соединить никаким набором кабелей) — MST в строгом смысле не существует, и по условию 3.2.3 ("Грабли") это должно быть явной ошибкой, а не молчаливым возвратом неполного дерева как готового результата.If `chosen.size() < n - 1` after processing every cable, the original graph was disconnected to begin with (some buildings can't be connected by any set of cables) — an MST doesn't exist in the strict sense, and per 3.2.3's Gotchas, this must be an explicit error, not a silent return of an incomplete tree as if it were the final result.
На маленьком примере (n=4) разница незаметна, но при масштабировании до реального кампуса с сотнями зданий отсутствие сжатия пути (`parent[x] = find(parent[x])` вместо простого рекурсивного вызова без записи) превращает `find` в потенциально O(V) на неудачно построенной цепочке union'ов — именно об этом предупреждал раздел "Грабли" в 3.2.3.On a small example (n=4) the difference is invisible, but scaling up to a real campus with hundreds of buildings, missing path compression (`parent[x] = find(parent[x])` instead of a plain recursive call with no write-back) turns `find` into potentially O(V) on an unluckily built union chain — exactly what 3.2.3's Gotchas section warned about.