prim

#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
typedef pair<int, int> p;

#define INF 999
#define max_size 10000

priority_queue<p, vector<p>, greater<p>> q;
vector<int> g[max_size];
vector<p> need;  //first wil be the parent,second the rank
int n, m;
vector<int> inMST; // if a vertice is already in MST or no

void read()
{
    ifstream in("file.txt");
    if (in.is_open())
    {
        in >> n >> m;
        int x, y, w;
        for (int i = 0; i<=n; i++)
        {
            g[i].assign(n+1, 0);
        }
        inMST.assign(n + 1, 0);

        for (int i = 0; i<m; i++)
        {
            in >> x >> y >> w;
            g[x][y] = w;
            g[y][x] = w;
        }
    }
    else
        cout << "Unable to open the file\n";

}

void prim()
{
    int source = 1;
    need.assign(n+1, { -1,INF });
    q.push({ 0,source });
    need[source].second = 0;

    while (!q.empty())
    {
        p e = q.top();
        int u=e.second;
        q.pop();
        inMST[u] = 1;
        for (int j = 1; j <= n; j++)
            {
                int v = j;
                int w = g[u][j];
                if (w!=0 && inMST[v] == 0 && need[v].second>w)
                {
                    need[v].second = w;
                    q.push({ need[v].second,v });
                    need[v].first = u;
                }

            }
    }


}
int main()
{
    read();
    prim();
    cout << "MST:\n";
    for (int i = 1; i<=n; i++)
        if(need[i].first!=-1)
            cout << need[i].first << " " << i<<endl;
    return 0;
}

/*
7 11
1 2 7
1 7 5
2 3 8
2 4 7
2 7 9
3 4 5
4 5 9
4 6 8
4 7 15
5 6 11
6 7 6

should print : 1 7,3 4,6 7,1 2,4 5,4 2
*/