• API
• FAQ
• Tools
• Archive
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.
Top