Josif_tepe

Untitled

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