This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Series-205/library
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A" #include <bits/stdc++.h> using namespace std; #include "../data-structure/union-find.cpp" int main() { int n, q; cin >> n >> q; UnionFind uf(n); for(int i = 0; i < q; i++) { int c, x, y; cin >> c >> x >> y; if(c) cout << uf.same(x, y) << "\n"; else uf.unite(x, y); } return 0; }
#line 1 "test/AOJ-DLS-1-A.test.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A" #include <bits/stdc++.h> using namespace std; #line 3 "data-structure/union-find.cpp" using namespace std; struct UnionFind { vector<int> data; UnionFind() = default; explicit UnionFind(size_t sz) : data(sz, -1) {} bool unite(int x, int y) { x = find(x); y = find(y); if(x == y) return false; if(data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); } int size(int x) { return -data[x]; } bool same(int x, int y) { return find(x) == find(y); } }; /* * @brief Union-Find * @docs docs/union-find.md */ #line 7 "test/AOJ-DLS-1-A.test.cpp" int main() { int n, q; cin >> n >> q; UnionFind uf(n); for(int i = 0; i < q; i++) { int c, x, y; cin >> c >> x >> y; if(c) cout << uf.same(x, y) << "\n"; else uf.unite(x, y); } return 0; }