Lesson8

#include <iostream>
#include <vector>

using namespace std;

class DSU {
 public:
  DSU(int n) : p(n), r(n) { for (int i = 0; i < n; ++i) p[i] = i; cout << "Constructor called\n"; }
  ~DSU() { cout << "Destructor called No ne nuzhen!\n"; }
  int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }
  bool Union(int x, int y) {
    x = Find(x); y = Find(y);
    if (x == y) return false;
    if (r[x] < r[y]) swap(x, y);
    p[y] = x;
    if (r[x] == r[y]) r[x]++;
    return true;
  }
 private:
  vector<int> p;
  vector<int> r;
};

int main() {
  {
    DSU dsu(10);
    dsu.Union(1, 2);
    dsu.Union(3, 4);
    dsu.Union(2, 7);
    for (int i = 0; i < 10; ++i)
      cout << dsu.Find(i) << " ";
    cout << "\n";
  }
  cout << "Hello world!\n";
  return 0;
}