tests/dsu.test.cpp

• View this file on GitHub
• Last update: 2025-01-22 03:51:11+00:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Disjoint set union (tools/dsu.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind

#include <iostream>
#include "tools/dsu.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;
  tools::dsu dsu(N);
  for (int q = 0; q < Q; ++q) {
    int t, u, v;
    std::cin >> t >> u >> v;
    if (t == 0) {
      dsu.merge(u, v);
    } else {
      std::cout << (dsu.same(u, v) ? 1 : 0) << '\n';
    }
  }

  return 0;
}

#line 1 "tests/dsu.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind

#include <iostream>
#line 1 "tools/dsu.hpp"



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

namespace tools {
  class dsu {
  private:
    // if this->m_data[x] < 0:
    //   x is a root.
    //   size(x) is -this->m_data[x].
    // if this->m_data[x] >= 0:
    //   x is an inner or leaf node.
    //   parent(x) is this->m_data[x].
    ::std::vector<int> m_data;

    int size() const {
      return this->m_data.size();
    }

  public:
    dsu() = default;
    dsu(const ::tools::dsu&) = default;
    dsu(::tools::dsu&&) = default;
    ~dsu() = default;
    ::tools::dsu& operator=(const ::tools::dsu&) = default;
    ::tools::dsu& operator=(::tools::dsu&&) = default;

    explicit dsu(const int n) : m_data(n, -1) {
    }

    int leader(const int x) {
      assert(0 <= x && x < this->size());

      return this->m_data[x] < 0 ? x : (this->m_data[x] = this->leader(this->m_data[x]));
    }

    bool same(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      return this->leader(x) == this->leader(y);
    }

    int merge(int x, int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      x = this->leader(x);
      y = this->leader(y);
      if (x == y) return x;

      if (this->m_data[x] > this->m_data[y]) ::std::swap(x, y);
      this->m_data[x] += this->m_data[y];
      this->m_data[y] = x;

      return x;
    }

    int size(const int x) {
      assert(0 <= x && x < this->size());

      return -this->m_data[this->leader(x)];
    }

    ::std::vector<::std::vector<int>> groups() {
      ::std::vector<::std::vector<int>> res(this->size());
      for (int i = 0; i < this->size(); ++i) {
        res[this->leader(i)].push_back(i);
      }
      res.erase(::std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }
  };
}


#line 5 "tests/dsu.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;
  tools::dsu dsu(N);
  for (int q = 0; q < Q; ++q) {
    int t, u, v;
    std::cin >> t >> u >> v;
    if (t == 0) {
      dsu.merge(u, v);
    } else {
      std::cout << (dsu.same(u, v) ? 1 : 0) << '\n';
    }
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	6 ms	4 MB
g++	max_random_00	AC	50 ms	4 MB
g++	max_random_01	AC	50 ms	4 MB
g++	max_random_02	AC	46 ms	4 MB
g++	path_00	AC	42 ms	4 MB
g++	path_01	AC	44 ms	4 MB
g++	path_02	AC	43 ms	4 MB
g++	path_03	AC	41 ms	4 MB
g++	random_00	AC	37 ms	4 MB
g++	random_01	AC	37 ms	4 MB
g++	random_02	AC	29 ms	4 MB
g++	random_03	AC	11 ms	4 MB
g++	random_04	AC	25 ms	4 MB
g++	random_05	AC	34 ms	4 MB
g++	random_06	AC	30 ms	4 MB
g++	random_07	AC	8 ms	4 MB
g++	random_08	AC	15 ms	4 MB
g++	random_09	AC	46 ms	4 MB

Back to top page