test/ds/dsu.test.cpp

• View this file on GitHub
• Last update: 2024-11-09 00:49:07+00:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

Depends on

• ds/dsu.hpp
• prelude.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

#include "prelude.hpp"
#include "ds/dsu.hpp"

int n, q, c, x, y;
int main() {
   scanf("%d%d", &n, &q);
   dsu dsu(n);
   while (q--) {
      scanf("%d%d%d", &c, &x, &y);
      if (c == 0) dsu.unite(x, y);
      else printf("%d\n", (int)dsu.same(x, y));
   }
}

#line 1 "test/ds/dsu.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

#line 2 "prelude.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vc = vector<char>;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
auto ndvec(int n, auto e) { return vector(n, e); }
auto ndvec(int n, auto ...e) { return vector(n, ndvec(e...)); }
auto comp_key(auto&& f) { return [&](auto&& a, auto&& b) { return f(a) < f(b); }; }
auto& max(const auto& a, const auto& b) { return a < b ? b : a; }
auto& min(const auto& a, const auto& b) { return b < a ? b : a; }
#if __cpp_lib_ranges
namespace R = std::ranges;
namespace V = std::views;
#endif
#line 3 "ds/dsu.hpp"

class dsu {
 public:
  dsu(int n) : par(n, -1), cnt(n) {}
  int count() const { return cnt; }
  void clear() {
    fill(par.begin(), par.end(), -1);
    cnt = par.size();
  }
  int find(int x) { return par[x] < 0 ? x : par[x] = (int)find(par[x]); }
  bool same(int x, int y) { return find(x) == find(y); }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (par[x] > par[y]) swap(x, y);
    par[x] += par[y], par[y] = x;
    cnt--;
    return true;
  }
  int size(int x) { return -par[find(x)]; }
  vector<vector<int>> groups() {
    vector<vector<int>> res(par.size());
    for (int x = 0; x < par.size(); x++) res[find(x)].push_back(x);
    res.erase(remove_if(all(res), [](const auto& v) { return v.empty(); }),
              res.end());
    return res;
  }

 private:
  vector<int> par;
  int cnt;
};
#line 5 "test/ds/dsu.test.cpp"

int n, q, c, x, y;
int main() {
   scanf("%d%d", &n, &q);
   dsu dsu(n);
   while (q--) {
      scanf("%d%d%d", &c, &x, &y);
      if (c == 0) dsu.unite(x, y);
      else printf("%d\n", (int)dsu.same(x, y));
   }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-12	00_small_00.in	AC	12 ms	8 MB
g++-12	00_small_01.in	AC	11 ms	8 MB
g++-12	01_rand_00.in	AC	12 ms	8 MB
g++-12	01_rand_01.in	AC	12 ms	8 MB
g++-12	01_rand_02.in	AC	12 ms	8 MB
g++-12	01_rand_03.in	AC	12 ms	8 MB
g++-12	01_rand_04.in	AC	12 ms	8 MB
g++-12	01_rand_05.in	AC	13 ms	8 MB
g++-12	02_linear_00.in	AC	12 ms	8 MB
g++-12	02_linear_01.in	AC	12 ms	8 MB
g++-12	02_linear_02.in	AC	15 ms	8 MB
g++-12	02_linear_03.in	AC	18 ms	8 MB
g++-12	03_grid_00.in	AC	12 ms	8 MB
g++-12	03_grid_01.in	AC	11 ms	8 MB
g++-12	03_grid_02.in	AC	12 ms	8 MB
g++-12	03_grid_03.in	AC	12 ms	8 MB
g++-12	03_grid_04.in	AC	12 ms	8 MB
g++-12	03_grid_05.in	AC	11 ms	8 MB
g++-12	03_grid_06.in	AC	12 ms	8 MB
g++-12	03_grid_07.in	AC	12 ms	8 MB
g++-12	03_grid_08.in	AC	12 ms	8 MB
g++-12	04_critical_00.in	AC	17 ms	8 MB
g++-12	04_critical_01.in	AC	17 ms	8 MB
g++-12	05_groups_00.in	AC	24 ms	8 MB
g++-12	05_groups_01.in	AC	24 ms	8 MB
g++-12	05_groups_02.in	AC	25 ms	8 MB
g++-12	05_groups_03.in	AC	25 ms	8 MB
g++-12	05_groups_04.in	AC	24 ms	8 MB
g++-12	06_randmax_00.in	AC	13 ms	8 MB
g++-12	06_randmax_01.in	AC	26 ms	8 MB
g++-12	06_randmax_02.in	AC	32 ms	8 MB
g++-12	06_randmax_03.in	AC	40 ms	8 MB

Back to top page