Hackerrank Kruskal (MST): Really Special Subtree Solution

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
vector<int> p(3001),rnk(3001,1);
int find(int a){
    return p[a]==a?a:p[a]=find(p[a]);
}
bool same(int a,int b){
    return find(a)==find(b);
}
void merge(int a,int b){
    /*if(!same(a,b))*/{
        if(rnk[find(a)]>rnk[find(b)]){
            // num[find(a)]+=num[find(b)];
            p[find(b)]=find(a);
        }
        else {
            // num[find(b)]+=num[find(a)];
            p[find(a)]=find(b);
        }
        if(rnk[find(a)]==rnk[find(b)])
            rnk[find(b)]++;
    }
}
int main(){
    int n,e;
    cin>>n>>e;
    for(int i=1;i<=n;i++)
        p[i]=i;
    vector<vector<int> > a;
    for(int i=0;i<e;i++){
        int x,y,w;
        cin>>x>>y>>w;
        a.push_back({w,x,y});
    }
    sort(a.begin(),a.end(),[](const vector<int> &l,const vector<int> &r){
        if(l[0]<r[0])
            return true;
        if(l[0]==r[0])
            return l[1]+l[2]<r[1]+r[2];
        return false;
    });
    int sum=0;
    for(int i=0;i<e;i++)
        if(!same(a[i][1],a[i][2])){
            merge(a[i][1],a[i][2]);
            sum+=a[i][0];
        }
    cout<<sum<<endl;
}

Comments