test/aoj/dsl_1_a.test.cpp

View this file on GitHub
Last update: 2023-06-20 08:00:22+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A

#include "src/cpp-template/header/int-alias.hpp"
#include "src/data-structure/disjoint-set-union.hpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n, q;
    std::cin >> n >> q;

    DisjointSetUnion d(n);
    while (q--) {
      usize com, x, y;
      std::cin >> com >> x >> y;

      if (not com) {
        d.merge(x, y);
      } else {
        std::cout << (d.same(x, y)) << std::endl;
      }
    }
  }

} // namespace luz

int main() {
  luz::main_();
}

#line 1 "test/aoj/dsl_1_a.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32 = std::int32_t;
  using i64 = std::int64_t;
  using u32 = std::uint32_t;
  using u64 = std::uint64_t;

}
#line 2 "src/data-structure/disjoint-set-union.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

}
#line 4 "src/data-structure/disjoint-set-union.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

namespace luz {

  class DisjointSetUnion {
    usize n;

    // vals[v] :=
    //   if v is root node: -1 * component size
    //   otherwise: parent node
    std::vector< isize > vals;

   public:
    DisjointSetUnion() = default;
    explicit DisjointSetUnion(usize n): n(n), vals(n, -1) {}

    usize leader(usize v) {
      if (vals[v] < 0) return v;
      return vals[v] = leader(vals[v]);
    }

    bool same(usize u, usize v) {
      return leader(u) == leader(v);
    }

    usize merge(usize u, usize v) {
      isize x = leader(u);
      isize y = leader(v);
      if (x == y) return x;

      if (-vals[x] < -vals[y]) std::swap(x, y);

      vals[x] += vals[y];
      vals[y] = x;
      return x;
    }

    usize group_size(usize v) {
      return -vals[leader(v)];
    }
  };

} // namespace luz
#line 5 "test/aoj/dsl_1_a.test.cpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n, q;
    std::cin >> n >> q;

    DisjointSetUnion d(n);
    while (q--) {
      usize com, x, y;
      std::cin >> com >> x >> y;

      if (not com) {
        d.merge(x, y);
      } else {
        std::cout << (d.same(x, y)) << std::endl;
      }
    }
  }

} // namespace luz

int main() {
  luz::main_();
}