» » Minimum Spanning Tree (Kruskal)

Minimum Spanning Tree (Kruskal)

   7:57 PM       

 
struct node {
    int u,v,w;
    bool operator  < ( const node &b) const{
        return w<b.w;
    }
}e[mx];
int pr[mx];

int find(int r) { return r==pr[r]?r:(pr[r]=find(pr[r])); }

int mst(int n,int m){
    int i,u,v,r=0;
    for(i=1;i<=n;i++) pr[i]=i;
    sort(e,e+m);
    for(i=0;i<m;i++) {
        u=find(e[i].u);
        v=find(e[i].v);
        if(u!=v) {
            r+=e[i].w;
            pr[u]=v;
        }
    }
    return r;
}