test/yj_unionfind.test.cpp

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include <cstdio>

#include "DataStructure/disjoint_set.cpp"

int main() {
  size_t n, q;
  scanf("%zu %zu", &n, &q);

  disjoint_set ds(n);
  for (size_t i = 0; i < q; ++i) {
    int t;
    size_t u, v;
    scanf("%d %zu %zu", &t, &u, &v);

    if (t == 0) {
      ds.unite(u, v);
    } else if (t == 1) {
      printf("%d\n", ds.equivalent(u, v)? 1: 0);
    }
  }
}

#line 1 "test/yj_unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include <cstdio>

#line 1 "DataStructure/disjoint_set.cpp"



/**
 * @brief 素集合データ構造
 * @author えびちゃん
 */

#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>

class disjoint_set {
public:
  using size_type = size_t;

private:
  mutable std::vector<intmax_t> M_c;

public:
  disjoint_set() = default;

  explicit disjoint_set(size_type n): M_c(n, -1) {}

  void reset() { M_c.assign(M_c.size(), -1); }

  size_type representative(size_type v) const {
    if (M_c[v] < 0) return v;
    return (M_c[v] = representative(M_c[v]));
  }

  bool unite(size_type u, size_type v) {
    u = representative(u);
    v = representative(v);
    if (u == v) return false;
    if (-M_c[u] > -M_c[v]) std::swap(u, v);
    M_c[v] += M_c[u];
    M_c[u] = v;
    return true;
  }

  bool equivalent(size_type u, size_type v) const {
    return (representative(u) == representative(v));
  }

  size_type size() const noexcept { return M_c.size(); }
  size_type count(size_type v) const {
    return -M_c[representative(v)];
  }
};


#line 6 "test/yj_unionfind.test.cpp"

int main() {
  size_t n, q;
  scanf("%zu %zu", &n, &q);

  disjoint_set ds(n);
  for (size_t i = 0; i < q; ++i) {
    int t;
    size_t u, v;
    scanf("%d %zu %zu", &t, &u, &v);

    if (t == 0) {
      ds.unite(u, v);
    } else if (t == 1) {
      printf("%d\n", ds.equivalent(u, v)? 1: 0);
    }
  }
}