Thuật toán Kruskal tìm cây khung nhỏ nhất (Minimum Spanning Tree)

Đề bài: http://vn.spoj.com/problems/QBMST/

Code C++:
Độ phức tạp: O(ElogV) = O(MlogN)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second

typedef long long ll;

int n, m, lab[10005];
vector<pair<ll, pair<int, int> > > edges;
ll sum, mincost;

int root(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = root(lab[u]);
}

void merge(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}

int main() {
    
    // reset
    edges.clear();
    sum = 0; mincost = 0;
    memset(lab, -1, sizeof lab);
    
    cin >> n >> m;
    
    for(int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        edges.pb(mp(w, mp(u, v)));
        sum += w;
    }
    
    sort(edges.begin(), edges.end());
    for(auto e : edges) {
        ll w = e.fi;
        int u = e.se.fi;
        int v = e.se.se;
        if (root(u) != root(v)) {
            merge(u, v);
            mincost += w;
        }
    }
    
    cout << mincost;
    
    return 0;
}

Happy coding