234
правки
Изменения
→Реализация
Ребро - структура из трех чисел - {откуда ребро, куда ребро, вес ребра}.
root - текущий корень.
особенность реализации: алгоритму не важна кратность ребер. поэтому при составлении нового графа они могут появится - это уменьшает асимптотику с <tex>O(V^2)</tex> до <tex>O(E)</tex>
проверяем, можно ли дойти из <tex>v</tex> до остальных вершин. Если можно - запускаем <tex>findMST</tex>
добавляем в newEdges ребро с концами в данных компонентах и весом e.w
res += findMST(zeroEdges, ComponentsCount, newComponents[root])
return res
=== Сложность ===
