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

• View this file on GitHub
• Last update: 2023-02-27 10:03:43-03:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Template.cpp
• bits/stdc++.h
• dsu/Compress.cpp
• dsu/DSU.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include "dsu/DSU.cpp"
#include "dsu/Compress.cpp"

#include "Template.cpp"

int32_t main() {
  iopt;

  int n, Q;
  cin >> n >> Q;

  using UF = lib::dsu::ByRank<lib::dsu::Compress>;

  UF uf(n);

  for(int i = 0; i < Q; i++) {
    int t, a, b;
    cin >> t >> a >> b;
    if(t == 0) uf.merge(a, b);
    else cout << (int)(uf[a] == uf[b]) << endl;
  }
}

#line 1 "tests/yosupo/unionfind-with-compression.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#line 1 "dsu/DSU.cpp"


#include <bits/stdc++.h>

namespace lib {
using namespace std;
namespace dsu {
struct RankDSU {
  mutable vector<int> r, sz;
  pair<int, int> last_merge_ = {-1, -1};
  bool last_swapped_ = false;
  int merges = 0;
  RankDSU() {}
  RankDSU(int n) : r(n), sz(n, 1) {
    iota(r.begin(), r.end(), 0);
  }
  virtual void clear() {
    iota(r.begin(), r.end(), 0);
    fill(sz.begin(), sz.end(), 1);
    last_merge_ = {-1, -1};
    merges = 0;
  }
  virtual int get(int i) const {
    return r[i] == i ? i : get(r[i]);
  }
  int operator[](int i) const {
    return get(i);
  }
  pair<int, int> last_merge() const {
    return last_merge_;
  }
  int n_comps() const { return (int)r.size() - merges; }
  virtual void merged(int u, int v) {}
  virtual int merge(int u, int v) {
    u = get(u), v = get(v);
    if(u == v) return 0;
    last_swapped_ = false;
    if(sz[u] > sz[v]) swap(u, v), last_swapped_ = true;
    r[u] = v;
    sz[v] += sz[u];
    last_merge_ = {u, v};
    merges++;
    merged(u, v);
    return 1;
  }
};

template<template<class> class ...Ts>
struct ByRankImpl;

template<template<class> class T, template<class> class ...Ts>
struct ByRankImpl<T, Ts...> {
  using type = T<typename ByRankImpl<Ts...>::type>;
};

template<>
struct ByRankImpl<> {
  using type = RankDSU;
};

template<template<class> class ...Ts>
using ByRank = typename ByRankImpl<Ts...>::type;
} // namespace dsu
} // namespace lib



#line 1 "dsu/Compress.cpp"


#line 4 "dsu/Compress.cpp"

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



#line 4 "tests/yosupo/unionfind-with-compression.test.cpp"

#line 2 "Template.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
#define TESTCASE(tn) cout << "Case #" << tn << ": "
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }

int floor2(int x, int y);
int ceil2(int x, int y) {
  if(y < 0) return ceil2(-x, -y);
  return x < 0 ? -floor2(-x, y) : (x + y - 1) / y;
}
int floor2(int x, int y) {
  if(y < 0) return floor2(-x, -y);
  return x < 0 ? -ceil2(-x, y) : x / y;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

#define TC_MAIN int32_t main() { iopt; int T; cin >> T; for(int i = 1; i <= T; i++) solve(i); }
#line 6 "tests/yosupo/unionfind-with-compression.test.cpp"

int32_t main() {
  iopt;

  int n, Q;
  cin >> n >> Q;

  using UF = lib::dsu::ByRank<lib::dsu::Compress>;

  UF uf(n);

  for(int i = 0; i < Q; i++) {
    int t, a, b;
    cin >> t >> a >> b;
    if(t == 0) uf.merge(a, b);
    else cout << (int)(uf[a] == uf[b]) << endl;
  }
}

Back to top page