kruskal_mst.cpp

// Kruskal's algorithm to find minimum spanning tree 
// O(mlog(m)) time complexity
// vertices start from 1 onwards
#include <bits/stdc++.h>
using namespace std;
const int INF=1e7;

class Graph{
    int v,e;
    vector<tuple<int,int,int>>edges;
    int *link,*size;
public:
    Graph(int v,int e);
    ~Graph(){
        delete [] link;
        delete [] size;
    }
    void addedge();
    int find(int x);
    bool same(int a,int b);
    void unite(int a,int b);
    void mst();
};

Graph::Graph(int v,int e){
    this->v=v;
    this->e=e;
    link=new int[v];
    size=new int[v];
    for(int i=0;i<v;i++){
        link[i]=i;
        size[i]=1;
    }
}
void Graph::addedge(){
    cout<<"Enter pair of adjacent vertices with weight\n";
    for(int i=0;i<e;i++){
        int a,b,w;
        cin>>a>>b>>w;
        a--,b--;
        edges.push_back(make_tuple(w,a,b));
    }
    sort(edges.begin(),edges.end());
}
int Graph::find(int x){
    // while(x!=link[x]) x=link[x];
    // return x;
    
    // Path compression
    if(x==link[x]) return x;
    return link[x]=find(link[x]);
}
bool Graph::same(int a,int b){
    return find(a)==find(b);
}
void Graph::unite(int a,int b){
    a=find(a);
    b=find(b);
    if(size[a]<size[b]) swap(a,b);
    size[a]+=size[b];
    link[b]=a;
}
void Graph::mst(){
    cout<<"mst formed is:\n";
    for(int i=0;i<e;i++){
        int a,b,w;
        tie(w,a,b)=edges[i];
        if(!same(a,b)){
            unite(a,b);
            cout<<a+1<<"--"<<b+1<<" : "<<w<<"\n";
        }
    }
}

int main() {
    int vertices,edges;
    cout<<"Enter no of vertices & edges\n";
    cin>>vertices>>edges;
    Graph g(vertices,edges);
    g.addedge();
    g.mst();
	return 0;
}


// input
/*
7 7
1 2 1
1 4 2
4 3 9
5 6 6
5 7 5
7 6 7
3 2 3
*/