Advertisement
Josif_tepe

Untitled

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