Изменения

=== Корректность ===

''' Замечания: '''

Из сделанных замечаний и леммы следует, что дерево <tex>T'</tex> — MST в <tex>G</tex>.

=== Реализация ===

обозначения:

Граф хранится в виде множества ребер + индекс корня.

Ребро - структура из трех чисел - {откуда ребро, куда ребро, вес ребра}.

root - текущий корень.

появится - это уменьшает асимптотику с <tex>O(V^2)</tex> до <tex>O(E)</tex>

int result = 0;

int minEdge[n]; // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью.

if (текущее ребро равно по весу минимальному, входящему в эту вершину)

zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to

if (можно дойти)

return res

int newComponents[n]; // будущие компоненты связности

edge newEdges[] //создаем массив ребер в новом графе с вершинами в сконденсированными компонентами

for each <tex>e \in</tex> zeroEdges

if (концы e лежат в разных компонентах связности)

добавляем в newEdges ребро с концами в данных компонентах и весом e.w

return res