提出 #45058376

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class UnionFind{
    public:
        int par[100009];
        int siz[100009];
        int rank[100009];
        void init(int n){
            for (int i = 0; i < n; i++){
                par[i] = -1;
                rank[i] = -1;
                siz[i] = -1;
            }
        }
        int root(int x){
            if (par[x] == -1){
                return x;
            }
            else {
                par[x] = root(par[x]);
                return par[x];
            }
        }
        bool same(int x, int y){
            return root(x) == root(y);
        }
        bool unite(int x, int y){
            int rx = root(x);
            int ry = root(y);
            if (rx == ry){
                return false;
            }
            if (rank[rx] < rank[ry]){
                swap(rx, ry);
            }
            par[ry] = rx;
            if (rank[rx] == rank[ry]){
                rank[rx] ++;
            }
            siz[rx] += siz[ry];
            return true;
        }
        int size(int x){
            return siz[root(x)];
        }
};
vector<int> a(100009);
vector<int> b(100009);
vector<int> c(100009);
int main(){
    int n, m;
    cin >> n >> m;
    UnionFind uf;
    uf.init(n);
    vector<pair<int, int>> edg;
    for (int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i] -= 1;
        b[i] -= 1;
        edg.push_back(make_pair(c[i], i));
    }
    int ans = 0;
    sort(edg.begin(), edg.end());
    for (int i = 0; i < m; i++){
        int idx = edg[i].second;
        if (uf.same(a[idx], b[idx]) == false){
            uf.unite(a[idx], b[idx]);
            ans += edg[i].first;
        }
    }
    cout << ans << endl;
}

提出情報

ジャッジ結果