tests/data-structure/unionfind/libchecker.test.cpp

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Union Find (Disjoint Set Union) (library/data-structure/unionfind.hpp)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#include "../../../cpp/library/data-structure/unionfind.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  asalib::ds::UnionFind uf(n);
  while (q--) {
    int t, u, v;
    cin >> t >> u >> v;
    if (t == 0) {
      uf.merge(u, v);
    }
    else {
      cout << (uf.same(u, v) ? 1 : 0) << endl;
    }
  }
  return 0;
}

#line 1 "tests/data-structure/unionfind/libchecker.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#line 2 "library/data-structure/unionfind.hpp"

#line 5 "library/data-structure/unionfind.hpp"
using namespace std;

namespace asalib {
  namespace ds {
    class UnionFind {
      private:
      // par_size[i] < 0: size
      // par_size[i] >= 0: parent
      vector<int> par_size;
      size_t siz;

      public:
      UnionFind(): siz(0) {}
      explicit UnionFind(size_t n) {
        siz = n;
        par_size.reserve(n);
        par_size.resize(n, -1);
      }

      void merge(size_t u, size_t v) {
        assert(0 <= u && u < par_size.size());
        assert(0 <= v && v < par_size.size());
        u = leader(u), v = leader(v);
        if (u == v) return;
        assert(par_size[u] < 0 && par_size[v] < 0);
        if (par_size[u] > par_size[v]) swap(u, v);
        // u is the larger group (-par_size[u] >= -par_size[v])
        par_size[u] += par_size[v];
        par_size[v] = u;
        --siz;
      }

      bool same(size_t u, size_t v) {
        assert(0 <= u && u < par_size.size());
        assert(0 <= v && v < par_size.size());
        return leader(u) == leader(v);
      }

      int leader(size_t x) {
        assert(0 <= x && x < par_size.size());
        if (par_size[x] < 0) return x;
        return par_size[x] = leader(par_size[x]);
      }

      int size(size_t x) {
        assert(0 <= x && x < par_size.size());
        return -par_size[leader(x)];
      }

      vector<vector<size_t>> groups() {
        vector<vector<size_t>> res(par_size.size());
        for (size_t i = 0; i < par_size.size(); ++i) res[leader(i)].push_back(i);
        res.erase(remove_if(res.begin(), res.end(), [](const vector<size_t>& v) {
                    return v.empty();
                  }),
                  res.end());
        return res;
      }

      size_t count() { return siz; }
    };
  }  // namespace ds
}  // namespace asalib
#line 8 "tests/data-structure/unionfind/libchecker.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  asalib::ds::UnionFind uf(n);
  while (q--) {
    int t, u, v;
    cin >> t >> u >> v;
    if (t == 0) {
      uf.merge(u, v);
    }
    else {
      cout << (uf.same(u, v) ? 1 : 0) << endl;
    }
  }
  return 0;
}

Back to top page