Kruskal algorithm

Question

I am trying to implement the Kruskal algorithm. I understand how the algorithm work on the paper but when I try to code it I don't know how to implement the function. Here is some code that I tried to implement. https://code.sololearn.com/ch9x3FbrGxE4/#cpp .
I will appreciate if someone can help me understanding how to implement it in c++.

Answer 1

For the Kruskal algorithm you need to implement a disjoint set structure. After that you just iterate over the edges in order of increasing weights, and add them to your tree if they connect two disjoint subsets of vertices.

You can find disjoint set implementations on SoloLearn or on outside internet, but of course it would be better for your understanding if you write your own.

Since sorting is much more basic thing, you can just use std::sort instead of implementing it yourself. (if you are not sure about how the sorting works, i'd suggest starting with implementing separately several sorting algorithms - mergesort, quicksort, heapsort, bucket sort, and then return to this problem without worrying about sorting)