Алгоритм Крускала в O (n log n)

Мне интересно узнать, как запустить алгоритм Крускала на O (n log n) в c ++. Я реализовал алгоритм с решением, которое работает на O (n ^ 2), и код для этого ниже.

Я знаю, что должно быть возможно запустить Kruskal на O (n log n), но я зашел в тупик относительно того, как это можно сделать. Буду признателен за любые советы.

#include <vector>
#include <algorithm>
#include <set>
using namespace std;

//sort by weight
bool sorting (vector<int> i, vector<int> j) {return i[2]<j[2];}

class Submap {
private:
set<int> finder;
public:
Submap(int x) {finder.insert(x);}
Submap(set<int> x) {finder = x;}
set<int> pointreturn() {return finder;}
//function to add new set to current tree
void add(set<int> np) {
finder.insert(np.begin(), np.end());

}
void add(int n) {
finder.insert(n);
}
int size() {return int(finder.size());}

//find function returns true if the value is not found
bool find(int x) {
if (finder.find(x) == finder.end())
return true;
else
return false;
}
};

class Map {
private:
vector<Submap> submaps;
public:
int find(int x) {
int finder = -1;
for(int i = 0; i < int(submaps.size()); i++) {
if(!submaps[i].find(x)) {
finder = i;
break;
}
}
return finder;
}
void newsubmap(int a, int b) {
set<int> nextset;
nextset.insert(a);
nextset.insert(b);
submaps.push_back(Submap(nextset));
}
void addendum(int a, int index) {
submaps[index].add(a);
}

Submap subfind(int i) {return submaps[i];}

void fuse(int index1, int index2) {
submaps[index1].add(submaps[index2].pointreturn());
vector<Submap> nextmaps;
for(int i = 0; i < int(submaps.size()); i++) {
if (i != index2)
nextmaps.push_back(submaps[i]);
}
submaps = nextmaps;
}
int size() {return submaps[0].size();}
};

Map kruskal (vector<vector<int>> &graph, int weight, int junct) {
//sort the graph
sort(graph.begin(), graph.end(), sorting);
Map currmap;

int usedweight = 0;
for(int i=0; i<graph.size(); i++) {
int a = currmap.find(graph[i][0]);
int b = currmap.find(graph[i][1]);

//the boolean expression here is false if both points are already in the same submap
if(a != b || a == -1) {

usedweight += graph[i][2];

//if neither point is in the map so far
if(a == -1 && b == -1) {
currmap.newsubmap(graph[i][0], graph[i][1]);
}

//if one point is in the map so far
else if (a != -1 && b == -1) {
currmap.addendum(graph[i][1], a);
}
else if (a == -1 && b != -1) {
currmap.addendum(graph[i][0], b);
}

//if both points are in the map, but different submaps
else {
currmap.fuse(a, b);
}
}
//if the first set in the map is spanning, the algorithm is done
if(currmap.size() == junct)
break;
}

return (currmap);
}