SHARE
TWEET

Untitled

a guest Feb 14th, 2020 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class DSU {
  2. private:
  3.   int n;
  4.   int *p;
  5.   int *sz;
  6.   vector<vector<int> *> elem;
  7.  
  8. public:
  9.   DSU(int n) : n(n) {
  10.     p = new int[n];
  11.     sz = new int[n];
  12.     elem.resize(n);
  13.     for (int i = 0; i < n; i++)
  14.       elem[i] = new vector<int>(1, i);
  15.     fill_n(sz, n, 1);
  16.     for (int i = 0; i < n; i++)
  17.       p[i] = i;
  18.   }
  19.  
  20.   ~DSU() {
  21.     delete[] p;
  22.     delete[] sz;
  23.   }
  24.  
  25.   int get(int v) {
  26.     if (v == p[v])
  27.       return v;
  28.     return p[v] = get(p[v]);
  29.   }
  30.  
  31.   inline void merge(int a, int b) {
  32.     a = get(a);
  33.     b = get(b);
  34.     if (a == b)
  35.       return;
  36.     if (sz[a] > sz[b])
  37.       swap(a, b);
  38.     sz[b] += sz[a];
  39.     p[a] = b;
  40.     for (int i = 0; i < sz[a]; i++)
  41.       elem[b]->pb((*elem[a])[i]);
  42.     delete elem[a];
  43.   }
  44.  
  45.   inline int size(int a) {
  46.     return sz[get(a)];
  47.   }
  48.  
  49.   inline vector<int> *getElem(int a) {
  50.     return elem[get(a)];
  51.   }
  52.  
  53.   inline bool equal(int a, int b) {
  54.     return get(a) == get(b);
  55.   }
  56. };
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