This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/icpc_library
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include "../../data_structure/dsu.hpp" #include "../../template/template.hpp" int main() { int n, q; std::cin >> n >> q; lib::dsu uf(n); while (q--) { int t, u, v; std::cin >> t >> u >> v; if (t == 0) { uf.merge(u, v); } else { std::cout << (int)uf.same(u, v) << '\n'; } } }
#line 1 "test/data_structure/Unionfind.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #line 2 "data_structure/dsu.hpp" #line 2 "template/template.hpp" #include <bits/stdc++.h> #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() using ll = long long; using ld = long double; using ull = unsigned long long; template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } namespace lib { using namespace std; } // namespace lib // using namespace lib; #line 4 "data_structure/dsu.hpp" namespace lib { struct dsu { public: dsu(int n = 0) : _n(n), data(n, -1) {} int leader(int a) { if (data[a] < 0) return a; return data[a] = leader(data[a]); } int merge(int a, int b) { int x = leader(a), y = leader(b); if (x == y) return x; if (-data[x] < -data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return x; } bool same(int a, int b) { return leader(a) == leader(b); } int size(int a) { return -data[leader(a)]; } private: int _n; vector<int> data; }; } // namespace lib #line 5 "test/data_structure/Unionfind.test.cpp" int main() { int n, q; std::cin >> n >> q; lib::dsu uf(n); while (q--) { int t, u, v; std::cin >> t >> u >> v; if (t == 0) { uf.merge(u, v); } else { std::cout << (int)uf.same(u, v) << '\n'; } } }