3.Prim's MST

Algorithm: (Implemented using Priority Queue)

1) Initialize keys of all vertices as infinite and 
   parent of every vertex as -1.

2) Create an empty priority_queue pq.  Every item
   of pq is a pair (weight, vertex). Weight (or 
   key) is used used as first item  of pair
   as first item is by default used to compare
   two pairs.

3) Initialize all vertices as not part of MST yet.
   We use boolean array inMST[] for this purpose.
   This array is required to make sure that an already
   considered vertex is not included in pq again. This
   is where Prims's implementation differs from Dijkstra.
   In Dijkstr's algorithm, we didn't need this array as
   distances always increase. We require this array here 
   because key value of a processed vertex may decrease
   if not checked.

4) Insert source vertex into pq and make its key as 0.

5) While either pq doesn't become empty 
    a) Extract minimum key vertex from pq. 
       Let the extracted vertex be u.

    b) Include u in MST using inMST[u] = true.

    c) Loop through all adjacent of u and do 
       following for every vertex v.

           // If weight of edge (u,v) is smaller than
           // key of v and v is not already in MST
           If inMST[v] = false && key[v] > weight(u, v)

               (i) Update key of v, i.e., do
                     key[v] = weight(u, v)
               (ii) Insert v into the pq 
               (iv) parent[v] = u
               
6) Print MST edges using parent array.

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n;
    cin >> m;

    vector<pair<int, int>> v[n + 1];

    for (int i = 1; i <= m; i++)
    {
        int a, b, w;
        cin >> a;
        cin >> b;
        cin >> w;

        v[a].push_back({b, w});
        v[b].push_back({a, w});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> key(n + 1, INT_MAX);
    vector<int> parent(n + 1, -1);
    vector<bool> vs(n + 1);
    pq.push({0, 1});
    key[1] = 0;

    while (!pq.empty())
    {
        int x = pq.top().second;
        pq.pop();

        if(vs[x]){
            continue;
        }

        vs[x] = 1;
        

        for (auto itr = v[x].begin(); itr != v[x].end(); itr++)
        {
            pair<int, int> p = *itr;
            if (vs[p.first] == 0 && p.second < key[p.first])
            {
                pq.push({p.second, p.first});
                key[p.first] = p.second;
                parent[p.first] = x;
            }
        }
    }

    int s = 0;

    for (int i = 1; i <= n; i++)
    {
        s = s + key[i];
    }
    cout << s;

    return 0;
}

Time complexity : O(E Log V)