C++ Library for Competitive Programming
/*
* @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;
}