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 M. N 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 $a_i$ , $b_i$, $w_i$ where $a_i$ and $b_i$ represents an edge from a vertex $a_i$ to a vertex $b_i$ and $w_i$ represents the weight of that edge.

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

Constraints:
$2\le N\le 10000$
$1\le M\le 100000$
$1\le a_i,b_i\le N$
$1\le w_i\le 1000$

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;

}