SHARE
TWEET

Untitled

a guest May 22nd, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. //  dsu.h
  3. //  sem9
  4. //
  5. //  Created by krymov on 14/12/2018.
  6. //  Copyright © 2018 krymov. All rights reserved.
  7. //
  8.  
  9. #ifndef dsu_h
  10. #define dsu_h
  11. #include <iostream>
  12. #include <vector>
  13. #include <stack>
  14.  
  15. class DSU {
  16. public:
  17.     DSU(size_t size) : arr(size), rank(size, 0) {
  18.         for (int i = 0; i < size; ++i) {
  19.             arr[i] = i;
  20.         }
  21.     }
  22.     void union_sets (int a, int b) {
  23.         a = find_set (a);
  24.         b = find_set (b);
  25.         if (a != b) {
  26.             if (size[a] < size[b])
  27.                 swap (a, b);
  28.             parent[b] = a;
  29.             rank[a] += rank[b];
  30.         }
  31.     }
  32.     int find_set(int v) {
  33.         assert(v < arr.size());
  34.         std::stack<int> q;
  35.         int cur = arr[v];
  36.         q.push(v);
  37.         while (cur != arr[cur]) {
  38.             q.push(arr[cur]);
  39.             cur = arr[cur];
  40.         }
  41.         int root = cur;
  42.         while (!q.empty()) {
  43.             arr[q.top()] = root;
  44.             q.pop();
  45.         }
  46.         return root;
  47.     }
  48.    
  49.     void union_set(int a, int b) {
  50.         assert(a < arr.size());
  51.         assert(b < arr.size());
  52.        
  53.         int set_a = find_set(a);
  54.         int set_b = find_set(b);
  55.        
  56.         if (set_a != set_b) {
  57.             if (rank[set_a] < rank[set_b]) {
  58.                 std::swap(set_a, set_b);
  59.             }
  60.             arr[set_b] = set_a;
  61.             if (rank[set_a] == rank[set_b]) {
  62.                 rank[set_a]++;
  63.             }
  64.         }
  65.     }
  66.    
  67. private:
  68.     std::vector<int> arr;
  69.     std::vector<int> rank;
  70. };
  71.  
  72. int main2(int argc, const char * argv[]) {
  73.     DSU dsu(10);
  74.     for (int i = 0; i < 10; ++i) {
  75.         std::cout << dsu.find_set(i) << std::endl;
  76.     }
  77.     for (int i = 0; i < 5; ++i) {
  78.         dsu.union_set(i, 9 - i);
  79.     }
  80.     std::cout << "-----------" << std::endl;
  81.     for (int i = 0; i < 10; ++i) {
  82.         std::cout << dsu.find_set(i) << std::endl;
  83.     }
  84.    
  85.     // insert code here...
  86.     std::cout << "Hello, World!\n";
  87.     return 0;
  88. }
  89.  
  90. #endif /* dsu_h */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top