This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub noshi91/Library
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include "data_structure/union_find.cpp" #include <iostream> int main() { #include "other/fast_ios.cpp" int n, q; std::cin >> n >> q; union_find uf(n); for (int i = 0; i != q; i += 1) { int t, u, v; std::cin >> t >> u >> v; switch (t) { case 0: { uf.unite(u, v); } break; case 1: { std::cout << uf.same(u, v) << "\n"; } break; } } }
#line 1 "test/union_find.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #line 2 "other/int_alias.cpp" #include <cstddef> #include <cstdint> using i32 = std::int32_t; using i64 = std::int64_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using isize = std::ptrdiff_t; using usize = std::size_t; #line 2 "data_structure/union_find.cpp" #include <cassert> #include <utility> #include <vector> class union_find { private: class node_type { friend union_find; usize parent; usize size; node_type(const usize parent, const usize size) : parent(parent), size(size) {} }; std::vector<node_type> tree; public: union_find() = default; explicit union_find(const usize n) : tree(n, node_type(n, 1)) {} usize size() const { return tree.size(); } usize find(const usize x) { assert(x < size()); if (tree[x].parent == size()) return x; else return tree[x].parent = find(tree[x].parent); } bool same(const usize x, const usize y) { assert(x < size()); assert(y < size()); return find(x) == find(y); } usize size(const usize x) { assert(x < size()); return tree[find(x)].size; } void unite(usize x, usize y) { assert(x < size()); assert(y < size()); x = find(x); y = find(y); if (x != y) { if (tree[x].size < tree[y].size) std::swap(x, y); tree[x].size += tree[y].size; tree[y].parent = x; } } }; /** * @brief Union Find * @see https://scrapbox.io/data-structures/Union_Find */ #line 4 "test/union_find.test.cpp" #include <iostream> int main() { #line 1 "other/fast_ios.cpp" std::ios::sync_with_stdio(false); std::cin.tie(nullptr); #line 9 "test/union_find.test.cpp" int n, q; std::cin >> n >> q; union_find uf(n); for (int i = 0; i != q; i += 1) { int t, u, v; std::cin >> t >> u >> v; switch (t) { case 0: { uf.unite(u, v); } break; case 1: { std::cout << uf.same(u, v) << "\n"; } break; } } }