MST with Kruskal

kruskal.cpp

//author: Abdul Matin

void init(int nodes)
{
    for(int i = 1; i <= nodes; i++) link[i] = i, size[i] = 1;
}

int root(int x)
{
    if(x != link[x]) return (link[x] = root(link[x]));

    return x;
}

bool same(int a, int b)
{
    return root(a) == root(b);
}

void unite(int a, int b)
{
    a = root(a);
    b = root(b);
    if(size[a] < size[b]) swap(a, b);
    size[a] += size[b];
    link[b] = a;
}

bool cmp(tuple <int, int, int> a, tuple <int, int, int> b)
{
    return get<2>(a) > get<2>(b);
}


int kruskal(vector< tuple <int, int, int> > edges ,int src, int end, int edgeNumber, int nodes){
    sort(edges.begin(), edges.end(), cmp);
    init(nodes);
    int ans = INT_MAX;
    for(auto x: edges){
        int a = get<0>(x);
        int b = get<1>(x);
        int weight = get<2>(x);
        if(!same(a, b)) {unite(a, b); ans = min(ans, weight);}
        if(same(src, end)) return ans;
    }
}