test/ds/dsu_short.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_short.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
using namespace std;

#include "../../src/ds/dsu_short.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.fa[dsu.find(u)] = dsu.find(v);
    } else {
      cout << (dsu.find(u) == dsu.find(v)) << "\n";
    }
  }
  return 0;
}

#line 1 "test/ds/dsu_short.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
using namespace std;

#line 1 "src/ds/dsu_short.hpp"
struct DSU {
  vector<int> fa;
  DSU(int n) : fa(n) { iota(ALL(fa), 0); }
  int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
};
#line 7 "test/ds/dsu_short.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.fa[dsu.find(u)] = dsu.find(v);
    } else {
      cout << (dsu.find(u) == dsu.find(v)) << "\n";
    }
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	44 ms	4 MB
g++	max_random_01	AC	44 ms	4 MB
g++	max_random_02	AC	43 ms	4 MB
g++	path_00	AC	36 ms	4 MB
g++	path_01	AC	39 ms	6 MB
g++	path_02	AC	36 ms	4 MB
g++	path_03	AC	38 ms	6 MB
g++	random_00	AC	33 ms	4 MB
g++	random_01	AC	33 ms	4 MB
g++	random_02	AC	27 ms	4 MB
g++	random_03	AC	9 ms	4 MB
g++	random_04	AC	23 ms	4 MB
g++	random_05	AC	31 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	42 ms	4 MB

Back to top page