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

prim.cpp

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

/* Works for Connected and undirected graph */
// https://www.geeksforgeeks.org/prims-algorithm-using-priority_queue-stl/

#define pp pair<int, int>

int N, MX = INT32_MAX;
vector<vector<pair<int,int>>> graph;

void prim(int src = 0){
  vector<int> dist(N, MX);
  vector<bool> inMST(N, false);
  priority_queue<pp, vector<pp>, greater<pp>> pq;
  dist[src] = 0;
  pq.push({0, src});
  while(!pq.empty()){
    auto p = pq.top();
    pq.pop();
    int u = p.second, d = p.first;
    if (dist[u] < d) continue;
    inMST[u] = true;
    for (auto V : graph[u]) {
      int v = V.first, weight = V.second;
      if (!inMST[v] && dist[v] > weight){
        dist[v] = weight;
        pq.push({dist[v], v});
      }
    }
  }
}