cay khung lon nhat

Code

#include <bits/stdc++.h>
#define int long long
#define pb push_back

using namespace std;
const int N = 1e4 + 5;
const int M = 15 * 1e3 + 5;

struct Edge{
    int u,v,w;
};

int n,m;
int u,v,c;
int cost = 0;
vector<Edge> E;
int p[N];
int sz[N];

bool cmp(Edge a, Edge b) {
    return (a.w < b.w);
}

int Find(int u) {
    if (u == p[u]) return u;
    else return p[u] = Find(p[u]);
}

void Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    p[v] = u;
    return;
}

void mst() {
    for (int i=1;i <= n;i++) {
        p[i] = i;
        sz[i] = 1;
    }
    sort(E.begin(), E.end(), cmp);
    int cnt = 0;
    for (int i=0;i < E.size() && cnt < n;i++) {
        Edge cur = E[i];
        u = cur.u;
        v = cur.v;
        if (Find(u) != Find(v)) {
            Union(u, v);
            cost += cur.w;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for (int i=1;i <= m;i++) {
        cin >> u >> v >> c;
        E.pb({u, v, c});
    }
    mst();
    cout << cost;
    return 0;
}