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); } } }