kruskal

//kruskal algorithm for MST
//time complexity O(m log m)
#include<bits/stdc++.h>
#define MAXM 100
#define pb push_back
using namespace std;

struct edge
{
    int u,v,w;
    //there is an edge between u and v of weight w
};

bool operator <(edge A, edge B)
{
    return A.w <B.w;
    //short edge according to weights
}
//edge list enough, no need for adjacency list
vector < edge > e;
//array to keep track of parents for union find.
int p[MAXM];

int find(int x)
{
    return (p[x]==x) ? x : find(p[x]);
    //if(p[x] == x) return x;
    //return p[x] = find(p[x]);
}

int kruskal(int n)
{
    sort(e.begin(), e.end());
    //if we do not store size in a variable before the loop,then it will get TLE
    //int sz = e.size();
    int ans = 0;
    for(int i=0; i<e.size(); i++)
    {
        if(find(e[i].u) != find(e[i].v))
        {
            //union
            p[e[i].u] = p[e[i].v];
            ans += e[i].w;
        }
    }
    return ans;
}

int main()
{
    int V,E;
    cout <<"Enter vertex and edges :";
    cin >> V >>E;//input vertex/node and edge
    cout <<"Enter per vertex to vertex and their weight:"<<endl;
    for(int i=1; i<=E; i++)
    {
        int u,v,w;
        cin >>u >>v >>w;//vertex to vertex and their weight
        edge get;
        get.u = u;
        get.v = v;
        get.w = w;
        e.pb(get);
    }
    cout<<"MST is" << kruskal(V) <<endl;
    return 0;
}