Minimum Cost Spanning Tree By Kruskal Algorithm using priority_queue in c++
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
int main()
{
int n,e;
while(cin>>n>>e&&n&&e)
{
int belongs[n];
for(int i=0;i<n;i++)
belongs[i]=i;
priority_queue< pair<int, ii> > EdgeList;
int u,v,w;
long long cost=0;
for(int i=0;i<e;i++)
{
cin>>u>>v>>w;
EdgeList.push(make_pair(-w,make_pair(u,v)));
cost+=w;
}
long long mst_cost=0;
vector<pair<int,int> > MST;
while (!EdgeList.empty())
{
pair<int, ii> front = EdgeList.top();
EdgeList.pop();
int X=front.second.first;
int Y=front.second.second;
//x=Find(belongs,x);
int x=belongs[X];
//y=Find(belongs,y);
int y=belongs[Y];
if(x!=y){
mst_cost += (-front.first);
cout<<X<<"-"<<Y<<endl;
MST.push_back(make_pair(X,Y));
//union1(belongs,x,y,n);
for(int i=0;i<n;i++){
if(belongs[i]==y)
belongs[i]=x;
}
}
}
cout<<cost-mst_cost<<endl;
cout<<"Minimum Cost Spanning Tree\n";
for(int i=0;i<MST.size();i++)
{
cout<<"Source "<<MST[i].first<<" Destination "<<MST[i].second<<endl;
}
}
return 0;
}
No comments:
Post a Comment