Primes Algo for MST🚩🚩

/*
->to find the MST using Prim's algorithm
Steps:-
	1)define the priority queue(pq) and push any arbitrary pair in it with {0,node}
	2)now ,run a loop till size of priority queue > 0
			->get the curr as from pq's top and also currweight from pq's top
			->now,if visi[pq] is true continue
			->else
				->mark curr as visited
				->add currweight to ans,here ans is the cost of MST
				->traverse,the adjacenecy list of curr
					->if child is not visited
						->push the pair of {childWeight,child} into the priority queue

	3)at last the MST will be printed,but while printing keep in mind that we start printing after the processing of first node has been completed for that we keep a is_first varible and make it false after the first node's processing completes.

	4)also,ans contains the total weight of the MST,we can return that if in question it is just asked to give the weight of MST


	Note:- Prim's algo is very much similar to dijkstra just the difference is that in dijkstra we push the sum of currDist and childWeight in priority queue while in Prim's we to not do any of the addition stuff here we just push the weigth of child.


Time Complexity :- O(E log V)
*/
vector<pair<ll, ll>> g[100001];
vector<ll> visi(100001, false);

void Prims(ll n) {

	priority_queue <
	pair<ll, pair<ll, ll>>,
	     vector <pair<ll, pair<ll, ll>>>,
	     greater <pair<ll, pair<ll, ll>> >> pq; //here,we are taking pair<int,Pait<int,int>> because we want to print the MST if in question just weight is asked use a queue with just the pair.

	bool first = true;
	vector<bool> visi(n, false);
	pq.push({0, { -1, 0}});//pushing the random vertex into the queue.
	ll ans = 0;


	while (pq.size() > 0) {
		int curr = pq.top().second.second;
		int par = pq.top().second.first;
		int w = pq.top().first;
		pq.pop();
		if (visi[curr])
			continue;
		visi[curr] = true;

		if (!first) {
			cout << "[" << curr << "-" << par << "@" << w << "]" << endl;
			ans += w;
		}
		first = false;
		for (auto itr : g[curr]) {
			if (visi[itr.first] == false)
				pq.push({itr.second, {curr, itr.first}});
		}
	}


	cout << "The weight of MST is :- " << ans << endl;

}