7. Graf II dan Topik Lainnya

#include <bits/stdc++.h>

using namespace std;

struct DSU {

   int n; // brp vertex

   vector<int> par; // parent edge

   vector<int> rank;

   DSU(int n) : n(n) {

       // di awal, semua verteks menunjuk ke dirinya sendiri

       par.assign(n+1, 0);

       for (int i = 1; i <= n; i++) par[i] = i;

       rank.assign(n+1, 1);

   }

   // cari wakil dari 1 elemen

   int rep(int x) {

       if (par[x] == x) {

           // dia wakil dari dirinya sendiri

           return x;

       } else {

           // rekursi ke parent-nya

           int r = rep(par[x]);

           par[x] = r; // path compression

           return r;

       }

   }

   // tambahin edge antara x dan y

   void join(int x, int y) {

       // cari wakil masing2

       x = rep(x), y = rep(y);

       // join yang kecil ke yang besar

       // kita mau x nya itu yang lebih besar

       if (rank[x] < rank[y]) {

           swap(x, y);

       }

       par[y] = x;

       rank[x] = max(rank[x], rank[y] + 1);

   }

   // cek apakah x dan y terhubung?

   bool check(int x, int y) {

       return (rep(x) == rep(y));

   }

};

int main() {

   int n, m;

   vector<pair<int, pair<int, int>>> edges;

   //          weight      u    v

   cin >> n >> m;

   for (int i = 1; i <= m; i++) {

       int u, v, w;

       cin >> u >> v >> w;

       edges.push_back({w, {u, v}});

   }

   // sort edge berdasarkan weight

   // sort(edges.begin(), edges.end());

   sort(edges.begin(), edges.end(), greater<>());

   DSU dsu(n);

   int total_weight = 0;

   for (auto [w, p] : edges) {

       if (dsu.check(p.first, p.second)) {

           continue;

       }

       total_weight += w;

       dsu.join(p.first, p.second);

   }

   cout << total_weight << "\n";

}