Krushkal's MST (Minimum Spanning Tree) - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

const int N = 3e5+7;
vector<vector<pair<int,int>>> MST(N);
int par[N];

int Find(int node) {
   if (par[node] == node)
      return node;
   return par[node] = Find(par[node]);
}

bool Union(int n1, int n2) {
   int a1 = Find(n1);
   int a2 = Find(n2);
   if (a1 == a2)
      return true;
   par[a1] = a2;
   return false;
}

int main() {
   SaveTime
   int n,m; cin >> n >> m;
   for (int i = 1; i <= n; i++)
      par[i] = i;
   vector<tuple<int,int,int>> graph(m);
   for (int i = 0; i < m; i++) {
      int a,b,w; cin >> a >> b >> w;
      graph[i] = {w,a,b};
   }
   sort(graph.begin(), graph.end());

   for (int i = 0; i < m; i++) {
      int a = get<1>(graph[i]), b = get<2>(graph[i]), w = get<0>(graph[i]);
      if (Union(a,b))
         continue;
      MST[a].push_back({w,b});
      MST[b].push_back({w,a});
   }
}