daily pastebin goal
3%
SHARE
TWEET

Untitled

a guest Aug 10th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4.  
  5. using std::vector
  6.  
  7.  
  8. struct DSU {
  9.     vector<int> prev;
  10.     vector<int> r;
  11.     DSU(int n) {
  12.         prev = vector<int>(n + 1);
  13.         for (int i = 0; i <= n; ++i) {
  14.             prev[i] = i;
  15.         }
  16.         r = vector<int>(n + 1, 1);
  17.     }
  18.     int get(int k) {
  19.         if (prev[k] != k)
  20.             prev[k] = get(prev[k]);
  21.         return prev[k];
  22.     }
  23.     bool equal(int x, int y) {
  24.         return get(x) == get(y);
  25.     }
  26.     void merge(int x, int y) {
  27.         if (equal(x, y)) {
  28.             return;
  29.         }
  30.         x = get(x);
  31.         y = get(y);
  32.         if (r[x] < r[y]) {
  33.             prev[x] = y;
  34.         } else {
  35.             prev[y] = x;
  36.             if (r[x] == r[y]) {
  37.                 ++r[x];
  38.             }
  39.         }
  40.     }
  41. };
  42.  
  43.  
  44. int main() {
  45.     int n;
  46.     cin >> n;
  47.     DSU d(n);
  48.     if (d.equal(1, 2));
  49.     d.merge(3, 5);
  50. }
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