This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp"
#include <cstdio>
using namespace std;
#define call_from_test
#include "../../../structure/union_find.cpp"
#undef call_from_test
int main() {
int N, Q; scanf("%d%d", &N, &Q);
UnionFind uf(N);
while(Q--) {
int t; scanf("%d", &t);
int x, y; scanf("%d%d", &x, &y);
if(t == 0) {
uf.unite(x, y);
}
if(t == 1) {
printf("%d\n", uf.same(x, y) ? 1 : 0);
}
}
}
#line 1 "verifying_test/AOJ/DSL_1_A/union_find.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp"
#include <cstdio>
using namespace std;
#define call_from_test
#line 2 "structure/union_find.cpp"
/**
* @brief Union-Find
* @docs docs/structure/union_find.md
*/
#include <algorithm>
#include <vector>
struct UnionFind {
private:
const int n;
int size_;
vector<int> uf;
public:
// 初期化 UnionFind uni(n) のように宣言すれば良い
UnionFind(int _n) : n(_n), size_(_n), uf(_n, -1) {}
void reset() {
size_ = n;
fill(uf.begin(), uf.end(), -1);
}
// find (木の根を求める)
int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
// x と y が同じ集合に属するかどうか
bool same(int x, int y) {return find(x) == find(y);}
// x が属する集合の要素数
int size(int x) {return -uf[find(x)];}
// 集合はいくつあるか
int size() {return size_;}
// x と y の属する集合を併合
bool unite(int x, int y) {
x = find(x); y = find(y);
if(x == y) return false;
size_--;
if(-uf[x] < -uf[y]) swap(x, y);
uf[x] += uf[y]; uf[y] = x;
return true;
}
};
#line 8 "verifying_test/AOJ/DSL_1_A/union_find.test.cpp"
#undef call_from_test
int main() {
int N, Q; scanf("%d%d", &N, &Q);
UnionFind uf(N);
while(Q--) {
int t; scanf("%d", &t);
int x, y; scanf("%d%d", &x, &y);
if(t == 0) {
uf.unite(x, y);
}
if(t == 1) {
printf("%d\n", uf.same(x, y) ? 1 : 0);
}
}
}