test/ds/dsu.test.cpp

• View this file on GitHub
• Last update: 2025-09-28 19:57:19+08:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• src/ds/dsu.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind
#include <bits/stdc++.h>
using namespace std;

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

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  DSU dsu(n);
  while (q--) {
    int op, u, v;
    cin >> op >> u >> v;
    if (op == 0) {
      dsu.merge(u, v);
    } else {
      cout << dsu.same(u, v) << "\n";
    }
  }
  return 0;
}

#line 1 "test/ds/dsu.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind
#include <bits/stdc++.h>
using namespace std;

#line 1 "src/ds/dsu.hpp"
// `fasiz[i]` 非负时表示 `i` 的父节点, 否则表示 `i` 所在集合的大小的负值.
struct DSU {
  vector<int> fasiz;
  DSU(int n) : fasiz(n, -1) {}
  int find(int x) { return fasiz[x] < 0 ? x : fasiz[x] = find(fasiz[x]); }
  bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (-fasiz[x] < -fasiz[y]) swap(x, y);
    fasiz[x] += fasiz[y];
    fasiz[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -fasiz[find(x)]; }
};
#line 6 "test/ds/dsu.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  DSU dsu(n);
  while (q--) {
    int op, u, v;
    cin >> op >> u >> v;
    if (op == 0) {
      dsu.merge(u, v);
    } else {
      cout << dsu.same(u, v) << "\n";
    }
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	42 ms	4 MB
g++	max_random_01	AC	42 ms	4 MB
g++	max_random_02	AC	39 ms	4 MB
g++	path_00	AC	36 ms	4 MB
g++	path_01	AC	36 ms	4 MB
g++	path_02	AC	34 ms	4 MB
g++	path_03	AC	33 ms	4 MB
g++	random_00	AC	32 ms	4 MB
g++	random_01	AC	32 ms	4 MB
g++	random_02	AC	26 ms	4 MB
g++	random_03	AC	10 ms	4 MB
g++	random_04	AC	21 ms	4 MB
g++	random_05	AC	29 ms	4 MB
g++	random_06	AC	25 ms	4 MB
g++	random_07	AC	7 ms	4 MB
g++	random_08	AC	12 ms	4 MB
g++	random_09	AC	40 ms	4 MB

Back to top page