dsa/graphs/mst | desc: kruskal minimum spanning tree mst

kruskal.cpp

#include <bits/stdc++.h>
using namespace std;

#define pp pair<int, pair<int, int>>

const int N = 2e5 + 5;
int arr[N];
int _find(int key);
void _union(int a, int b);

bool myComparator(const pp &a, const pp &b){
  return a.second.second < b.second.second;
}

void kruskal(vector<pp> edgeList){
  sort(edgeList.begin(), edgeList.end(), myComparator);
  vector<pp> edgesInMST;
  for(auto edge : edgeList){
    auto a = edge.first;
    auto b = edge.second.first;
    auto weight = edge.second.second;
    if (_find(a) != _find(b)) {
        _union(a, b);
        edgesInMST.push_back({a, {b, weight}});
    }
  }
}