test/yosupo/unionfind.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Union-Find (src/DataStructure/UnionFind.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/DataStructure/UnionFind.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, Q;
 cin >> N >> Q;
 UnionFind uf(N);
 while (Q--) {
  int t, u, v;
  cin >> t >> u >> v;
  if (t) cout << uf.connected(u, v) << '\n';
  else uf.unite(u, v);
 }
 return 0;
}

#line 1 "test/yosupo/unionfind.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/DataStructure/UnionFind.hpp"
#include <vector>
#include <algorithm>
class UnionFind {
 std::vector<int> par;
public:
 UnionFind(int n): par(n, -1) {}
 int leader(int u) { return par[u] < 0 ? u : par[u]= leader(par[u]); }
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par[u] > par[v]) std::swap(u, v);
  return par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
};
#line 6 "test/yosupo/unionfind.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, Q;
 cin >> N >> Q;
 UnionFind uf(N);
 while (Q--) {
  int t, u, v;
  cin >> t >> u >> v;
  if (t) cout << uf.connected(u, v) << '\n';
  else uf.unite(u, v);
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	6 ms	4 MB
g++-13	max_random_00	AC	42 ms	4 MB
g++-13	max_random_01	AC	43 ms	4 MB
g++-13	max_random_02	AC	39 ms	4 MB
g++-13	path_00	AC	37 ms	4 MB
g++-13	path_01	AC	38 ms	4 MB
g++-13	path_02	AC	36 ms	4 MB
g++-13	path_03	AC	36 ms	4 MB
g++-13	random_00	AC	33 ms	4 MB
g++-13	random_01	AC	34 ms	4 MB
g++-13	random_02	AC	27 ms	4 MB
g++-13	random_03	AC	10 ms	4 MB
g++-13	random_04	AC	22 ms	4 MB
g++-13	random_05	AC	30 ms	4 MB
g++-13	random_06	AC	27 ms	4 MB
g++-13	random_07	AC	8 ms	4 MB
g++-13	random_08	AC	12 ms	4 MB
g++-13	random_09	AC	39 ms	4 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	max_random_00	AC	42 ms	4 MB
clang++-18	max_random_01	AC	44 ms	4 MB
clang++-18	max_random_02	AC	39 ms	4 MB
clang++-18	path_00	AC	37 ms	4 MB
clang++-18	path_01	AC	39 ms	4 MB
clang++-18	path_02	AC	38 ms	4 MB
clang++-18	path_03	AC	37 ms	4 MB
clang++-18	random_00	AC	33 ms	4 MB
clang++-18	random_01	AC	33 ms	4 MB
clang++-18	random_02	AC	27 ms	4 MB
clang++-18	random_03	AC	11 ms	4 MB
clang++-18	random_04	AC	22 ms	4 MB
clang++-18	random_05	AC	30 ms	4 MB
clang++-18	random_06	AC	26 ms	4 MB
clang++-18	random_07	AC	8 ms	4 MB
clang++-18	random_08	AC	13 ms	4 MB
clang++-18	random_09	AC	41 ms	4 MB

Back to top page