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

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

const int N = 1e5+7;
vector<pair<int,int> > adj[N];
vector<pair<int,int> > MST[N];
bool V[N];

int main() {
    SaveTime
    int n,m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a,b,w; cin >> a >> b >> w;
        adj[a].push_back({w,b});
        adj[b].push_back({w,a});
    }
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
    pq.push({0,{0,1}});
    while(!pq.empty()){
        int ch=pq.top().second.second,par=pq.top().second.first,c=pq.top().first;
        pq.pop();
        if(V[ch]) continue;
        V[ch]=true;
        for(auto pi: adj[ch]){
            if(pi.second!=par&&!V[pi.second]){
                pq.push({pi.first,{ch,pi.second}});
            }
        }
        if(par){
            ans+= c;
            MST[ch].push_back({c,par});
            MST[par].push_back({c,ch});
        }
    }
}