Advertisement
Josif_tepe

Untitled

Oct 24th, 2023
765
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5. const int maxn = 1e5 + 10;
  6. const int INF = 1e9;
  7. int root[maxn];
  8. int sz[maxn];
  9. int find_root(int x) {
  10.     while(root[x] != x) {
  11.         root[x] = root[root[x]];
  12.         x = root[x];
  13.     }
  14.     return x;
  15. }
  16. bool check(int A, int B) {
  17.     int root_A = find_root(A);
  18.     int root_B = find_root(B);
  19.     return root_A == root_B;
  20. }
  21. void unite(int A, int B) {
  22.     int root_A = find_root(A);
  23.     int root_B = find_root(B);
  24.     if(root_A != root_B) {
  25.         if(sz[root_A] > sz[root_B]) {
  26.             root[root_B] = root[root_A];
  27.             sz[root_A] += sz[root_B];
  28.         }
  29.         else {
  30.             root[root_A] = root[root_B];
  31.             sz[root_B] += sz[root_A];
  32.         }
  33.     }
  34.    
  35.    
  36. }
  37. int main() {
  38.     for(int i = 0; i < maxn; i++) {
  39.         root[i] = i;
  40.         sz[i] = 1;
  41.     }
  42.    
  43.     int n, m;
  44.     cin >> n >> m;
  45.     vector<pair<int, pair<int, int> > > v;
  46.     for(int i = 0; i < m; i++) {
  47.         int a, b, c;
  48.         cin >> a >> b >> c;
  49.         v.push_back(make_pair(c, make_pair(a, b)));
  50.     }
  51.     sort(v.begin(), v.end());
  52.     int MST = 0;
  53.     for(int i = 0; i < n; i++) {
  54.         int a = v[i].second.first;
  55.         int b = v[i].second.second;
  56.         int c = v[i].first;
  57.        
  58.         if(!check(a, b)) {
  59.             unite(a, b);
  60.             MST += c;
  61.         }
  62.     }
  63.     cout << MST << endl;
  64.     return 0;
  65. }
  66.  
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement