data-structure/test/Unionfind.test.cpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Disjoint Set Union (with Rank and Path Compression) (data-structure/dsu.hpp)

Code

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

#include <bits/extc++.h>

using namespace std;

#include "../dsu.hpp"

signed main() {
  int n, q;
  cin >> n >> q;
  dsu uf(n);
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t)
      cout << uf.same(x, y) << '\n';
    else
      uf.merge(x, y);
  }
}

#line 1 "data-structure/test/Unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include <bits/extc++.h>

using namespace std;

#line 1 "data-structure/dsu.hpp"
struct dsu {
 public:
  dsu(int n) : n(n), p(n, -1) {}

  int merge(int a, int b) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    int x = head(a), y = head(b);
    if (x == y) return x;
    if (-p[x] < -p[y]) swap(x, y);
    p[x] += p[y];
    p[y] = x;
    return x;
  }

  bool same(int a, int b) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    return head(a) == head(b);
  }

  int head(int a) {
    assert(0 <= a && a < n);
    if (p[a] < 0) return a;
    return p[a] = head(p[a]);
  }

  int size(int a) {
    assert(0 <= a && a < n);
    return -p[head(a)];
  }

  vector<vector<int>> groups() {
    vector<int> tmp(n), sz(n);
    for (int i = 0; i < n; ++i) tmp[i] = head(i), ++sz[tmp[i]];
    vector<vector<int>> gr(n);
    for (int i = 0; i < n; ++i) gr[i].reserve(sz[i]);
    for (int i = 0; i < n; ++i) gr[tmp[i]].push_back(i);
    gr.erase(remove_if(begin(gr), end(gr),
                       [&](const vector<int>& v) { return v.empty(); }),
             end(gr));
    return gr;
  }

 private:
  int n;
  vector<int> p;
};
#line 8 "data-structure/test/Unionfind.test.cpp"

signed main() {
  int n, q;
  cin >> n >> q;
  dsu uf(n);
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t)
      cout << uf.same(x, y) << '\n';
    else
      uf.merge(x, y);
  }
}

Back to top page