This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #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, u, v; scanf("%d%d%d", &t, &u, &v); if(t == 0) uf.unite(u, v); else printf("%d\n", uf.same(u, v) ? 1 : 0); } return 0; }
#line 1 "verifying_test/yosupo/data_structure/unionfind/union_find.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #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/yosupo/data_structure/unionfind/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, u, v; scanf("%d%d%d", &t, &u, &v); if(t == 0) uf.unite(u, v); else printf("%d\n", uf.same(u, v) ? 1 : 0); } return 0; }