データ構造/素集合データ構造/union-find
(test/data_structure/union-find/union-find.test.cpp)

• View this file on GitHub
• Last update: 2023-02-26 01:10:01+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

Depends on

• union-find (include/emthrm/data_structure/union-find/union-find.hpp)

Code

/*
 * @title データ構造/素集合データ構造/union-find
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A
 */

#include <iostream>

#include "emthrm/data_structure/union-find/union-find.hpp"

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::UnionFind union_find(n);
  while (q--) {
    int com, x, y;
    std::cin >> com >> x >> y;
    if (com == 0) {
      union_find.unite(x, y);
    } else if (com == 1) {
      std::cout << union_find.is_same(x, y) << '\n';
    }
  }
  return 0;
}

#line 1 "test/data_structure/union-find/union-find.test.cpp"
/*
 * @title データ構造/素集合データ構造/union-find
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A
 */

#include <iostream>

#line 1 "include/emthrm/data_structure/union-find/union-find.hpp"



#include <utility>
#include <vector>

namespace emthrm {

struct UnionFind {
  explicit UnionFind(const int n) : data(n, -1) {}

  int root(const int ver) {
    return data[ver] < 0 ? ver : data[ver] = root(data[ver]);
  }

  bool unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (data[u] > data[v]) std::swap(u, v);
    data[u] += data[v];
    data[v] = u;
    return true;
  }

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

  int size(const int ver) { return -data[root(ver)]; }

 private:
  std::vector<int> data;
};

}  // namespace emthrm


#line 10 "test/data_structure/union-find/union-find.test.cpp"

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::UnionFind union_find(n);
  while (q--) {
    int com, x, y;
    std::cin >> com >> x >> y;
    if (com == 0) {
      union_find.unite(x, y);
    } else if (com == 1) {
      std::cout << union_find.is_same(x, y) << '\n';
    }
  }
  return 0;
}

Back to top page