test/yosupo/unionfind.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include "include/mtl/unionfind.hpp"
#include <iostream>
using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);

  int N,Q; cin>>N>>Q;
  UnionFind uf(N);

  for (int q = 0; q < Q; q++) {
    int t; cin>>t;
    int u,v; cin>>u>>v;
    if (t == 0) {
      uf.unite(u,v);
    } else if (t == 1) {
      int ans = uf.are_union(u,v) ? 1 : 0;
      cout << ans << endl;
    }
  }

  return 0;
}

#line 1 "test/yosupo/unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#line 2 "include/mtl/unionfind.hpp"
#include <vector>
#include <numeric>
#include <cstddef>

class UnionFind {
 private:
  // par_[i] = { size if par_[i] < 0, root otherwise }
  std::vector<int> par_;

 public:
  UnionFind() = default;
  explicit UnionFind(size_t size) : par_(size, -1) {}

  int root(int u) {
    if (par_[u] < 0)
      return u;
    return par_[u] = root(par_[u]);
  }

  bool are_union(int u, int v) {
    return root(u) == root(v);
  }

  int size_of(int u) {
    return -par_[root(u)];
  }

  bool unite(int u, int v) {
    if (are_union(u,v))
      return false;
    if (size_of(u) < size_of(v))
      std::swap(u,v);
    par_[root(u)] -= size_of(v);
    par_[root(v)] = root(u);
    return true;
  }
};
#line 3 "test/yosupo/unionfind.test.cpp"
#include <iostream>
using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);

  int N,Q; cin>>N>>Q;
  UnionFind uf(N);

  for (int q = 0; q < Q; q++) {
    int t; cin>>t;
    int u,v; cin>>u>>v;
    if (t == 0) {
      uf.unite(u,v);
    } else if (t == 1) {
      int ans = uf.are_union(u,v) ? 1 : 0;
      cout << ans << endl;
    }
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	6 ms	3 MB
g++	max_random_00	AC	131 ms	4 MB
g++	max_random_01	AC	155 ms	4 MB
g++	max_random_02	AC	164 ms	3 MB
g++	path_00	AC	89 ms	4 MB
g++	path_01	AC	91 ms	4 MB
g++	path_02	AC	31 ms	4 MB
g++	path_03	AC	30 ms	4 MB
g++	random_00	AC	98 ms	4 MB
g++	random_01	AC	97 ms	4 MB
g++	random_02	AC	76 ms	4 MB
g++	random_03	AC	22 ms	4 MB
g++	random_04	AC	67 ms	4 MB
g++	random_05	AC	92 ms	4 MB
g++	random_06	AC	76 ms	4 MB
g++	random_07	AC	12 ms	4 MB
g++	random_08	AC	35 ms	4 MB
g++	random_09	AC	123 ms	4 MB
clang++	example_00	AC	6 ms	3 MB
clang++	max_random_00	AC	131 ms	4 MB
clang++	max_random_01	AC	131 ms	4 MB
clang++	max_random_02	AC	126 ms	4 MB
clang++	path_00	AC	90 ms	4 MB
clang++	path_01	AC	89 ms	4 MB
clang++	path_02	AC	34 ms	4 MB
clang++	path_03	AC	33 ms	4 MB
clang++	random_00	AC	131 ms	4 MB
clang++	random_01	AC	98 ms	4 MB
clang++	random_02	AC	82 ms	4 MB
clang++	random_03	AC	22 ms	4 MB
clang++	random_04	AC	66 ms	4 MB
clang++	random_05	AC	93 ms	4 MB
clang++	random_06	AC	73 ms	4 MB
clang++	random_07	AC	12 ms	4 MB
clang++	random_08	AC	35 ms	4 MB
clang++	random_09	AC	129 ms	4 MB

Back to top page