Kruskal Algorithm.

//No one born perfect :)
//Kruskal Algorithm
//Finding MST (Minimum Spanning Tree)
//Greedy Algo
//O(ElogE or ElogV)
//DS use DisJoint DS (Union Find)(very important DS)
//How it is work ? (We are considering that Graph is connected )
// a). First Sort all edge in increasing order according to weight
// b). Now Iterate each edge(u,v) in Edges and check whether these
// vertax u and v are in same tree or not (which we are finding using union and find method)
// if not include this edge otherwise continue (For more understanding see source code)
//  c). You will get a MST in end.
//For proof go wiki page:-
// https://en.wikipedia.org/wiki/Kruskal%27s_algorithm#Proof_of_correctness
// Happy Coding.
/////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>

#include <cstdio>

#include <list>

#include <cstring>

using namespace std;

// vector<vector <long int,long int> >v[100005];

int parent[200055];

int parentRank[200055]; // use for path comprasion algo making union it will reduce  time to loglogn ;)

struct edge{

int vertex1;

int vertex2;

int weight;

};

bool compare(edge a,edge b)

{

if(a.weight > b.weight)

return false;

else

{

return true;

}

}

int find(int node)                    //Find function. Finding parent of a node(vertex).

{

if(parent[node] == node)

return node;

return find(parent[node]);       //recursive search.

}

int  union_fun(int xNode,int yNode,int weight)

{

int xParent = find(xNode);

int yParent = find(yNode);

if(xParent == yParent)

return 0;

if(parentRank[xParent] > parentRank[yParent])

parent[yNode] = xParent;

else if(parentRank[xParent] < parentRank[yParent])

parent[xNode] = yParent;

else

{

parent[xNode] = yParent;

parentRank[yParent]++;

}

return weight;

}

int main()

{

int n,m;

cin>>n>>m;

edge Edge[m+1];

for(int i=0;i<m;i++)

{

cin>>Edge[i].vertex1>>Edge[i].vertex2>>Edge[i].weight;

}

sort(Edge,Edge+m,compare);

for(int i=1;i<=n;i++) //Make-Set function

{

parent[i]=i;

parentRank[i]=0;

}

int ans=0;

for(int i=0;i<m;i++)

{

ans += union_fun(Edge[i].vertex1,Edge[i].vertex2,Edge[i].weight);

}

cout<<ans<<endl;

return 0;

}