dsu/Compress.cpp

• View this file on GitHub
• Last update: 2023-02-27 10:03:35-03:00

Depends on

• bits/stdc++.h

Verified with

• tests/yosupo/unionfind-with-compression.test.cpp

Code

#ifndef _LIB_DSU_COMPRESS
#define _LIB_DSU_COMPRESS
#include <bits/stdc++.h>

namespace lib {
using namespace std;
namespace dsu {

template<typename D>
struct Compress : public D {
  using D::r;

  Compress() : D() {}
  Compress(int n) : D(n) {}

  virtual int get(int i) const override {
    return r[i] == i ? i : r[i] = get(r[i]);
  }
};
} // namespace dsu
} // namespace lib

#endif

#line 1 "dsu/Compress.cpp"


#include <bits/stdc++.h>

namespace lib {
using namespace std;
namespace dsu {

template<typename D>
struct Compress : public D {
  using D::r;

  Compress() : D() {}
  Compress(int n) : D(n) {}

  virtual int get(int i) const override {
    return r[i] == i ? i : r[i] = get(r[i]);
  }
};
} // namespace dsu
} // namespace lib

Back to top page