Minimum Spanning Tree

 Problem:-

Given a weighted undirected graph. Find the sum of weights of edges of a Minimum Spanning Tree.

Input:
Given 2 integers N and MN represents the number of vertices in the graph. M represents the number of edges between any 2 vertices.
Then M lines follow, each line has 3 space separated integers 

ai

 , 

bi

wi

 where 

ai

 and 

bi

 represents an edge from a vertex 

ai

 to a vertex 

bi

 and 

wi

 represents the weight of that edge.

Output:
Print the summation of edges weights in the MST.

Constraints:

2N10000


1M100000


1ai,biN


1wi1000

Sample Input
4 5
1 2 7
1 4 6
4 2 9
4 3 8
2 3 6
Sample Output
19
Time Limit: 5
Memory Limit: 256
Source Limit:

Code:-

#include<bits/stdc++.h>
using namespace std;
struct edge
{
int a ,w,b;
};
edge arr[1000000];
int parent[10001];

// function for compare the weight for sorting
bool comparetor(edge a,edge b)
{
if(a.w<b.w)
return true;
return false;
}

// function for find the parent
int find(int a)
{
if(parent[a]==-1)
return a;
else
return find(parent[a]);
}

// function for merge two nodes
void merge(int a,int b)
{
parent[a]=b;
}

// driver function
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
int a,b,w,sum=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
parent[i]=-1;
for(int i=0;i<m;i++)
{
cin>>arr[i].a>>arr[i].b>>arr[i].w;
}

// sort the array on the basis of weight
sort(arr,arr+m,comparetor);
for(int i=0;i<m;i++)
{
a=find(arr[i].a);
b=find(arr[i].b);

// if parents of both the nodes are not same
if(a!=b)
{
sum=sum+arr[i].w;
// merge both nodes means create a edge between both node
merge(a,b);
}
}
cout<<sum;
}



Leave a Reply

Your email address will not be published.