How it works?

Поддерживайте логическое значение inTree для каждой вершины. Начните с того, что в дереве находится только вершина 0. Граница — это каждое ребро, у которого ровно один конец находится внутри дерева, называемое пересекающим ребром.

Пошаговый процесс:

1. Среди всех пересекающих ребер выберите то, которое имеет наименьший вес.
2. Добавьте его внешнюю конечную вершину в дерево и прибавьте его вес к общей сумме.
3. Повторяйте до тех пор, пока дерево не будет содержать все n вершин (это займет n - 1 ребер).

Если в какой-то момент пересекающих ребер не останется, но вершины вне дерева еще будут, значит, граф несвязен.

Пример с ребрами [0,1,1, 1,2,2, 2,3,3, 0,3,4]: из 0 возьмите 0-1(1), затем 1-2(2), затем 2-3(3); итого 6.