Advertisement
Josif_tepe

Untitled

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