Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using std::vector
- struct DSU {
- vector<int> prev;
- vector<int> r;
- DSU(int n) {
- prev = vector<int>(n + 1);
- for (int i = 0; i <= n; ++i) {
- prev[i] = i;
- }
- r = vector<int>(n + 1, 1);
- }
- int get(int k) {
- if (prev[k] != k)
- prev[k] = get(prev[k]);
- return prev[k];
- }
- bool equal(int x, int y) {
- return get(x) == get(y);
- }
- void merge(int x, int y) {
- if (equal(x, y)) {
- return;
- }
- x = get(x);
- y = get(y);
- if (r[x] < r[y]) {
- prev[x] = y;
- } else {
- prev[y] = x;
- if (r[x] == r[y]) {
- ++r[x];
- }
- }
- }
- };
- int main() {
- int n;
- cin >> n;
- DSU d(n);
- if (d.equal(1, 2));
- d.merge(3, 5);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement