#include
#include
#define inf 1e9
using namespace std;
class Graph{
public:
int v;
list<pair<int,int> >*adj;
Graph(int v){
this->v=v;
adj=new list<pair<int,int> >[v];
}
void addEdge(int u,int v,int w){
adj[u].push_back(make_pair(v,w));
adj[v].push_back(make_pair(v,w));
}
int findMinVertex(int*weight,bool*visited,int v){
int minVertex=-1;
for(int i=0;i<v;i++){
if(!visited[i] and (minVertex=-1 or weight[i]<weight[minVertex])){
minVertex=i;
}
}
return minVertex;
}
void Prims(){
bool *visited=new bool[v];
int *parent=new int[v];
int*weight=new int[v];
for(int i=0;i<v;i++){
visited[i]=false;
weight[i]=false;
}
parent[0]=-1;
weight[0]=0;
for(int i=0;i<v;i++){
int minVertex=findMinVertex(weight,visited,v);
visited[minVertex]=true;
for(auto nbr:adj[minVertex]){
if(!visited[nbr.first]){
if(weight[nbr.first]>nbr.second){
parent[nbr.first]=minVertex;
weight[nbr.first]=nbr.second;
}
}
}
}
for(int i=0;i<v;i++){
cout<<i<<"--"<<parent[i]<<"with weight"<<weight[i]<<endl;
}
}
};
int main(){
int n,e;
cin>>n>>e;
Graph g(n);
// Edge*input=new Edge[e];
for(int i=0;i<e;i++)
{
int s,d,w;
cin>>s>>d>>w;
g.addEdge(s,d,w);
}
g.Prims();
}
my output is not correct for input:
7
8
0 3 4
0 1 6
1 2 5
3 2 7
3 4 2
4 5 4
5 6 1
4 6 3