This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#include <bits/stdc++.h> #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include "../../datastructure/unionfind.hpp" int main() { int n, q; std::cin >> n >> q; unionfind uf(n); while (q--) { int t, u, v; std::cin >> t >> u >> v; if (t == 0) { uf.unite(u, v); } if (t == 1) { std::cout << int(uf.find(u, v)) << '\n'; } } }
#line 1 "test/library-checker/unionfind.test.cpp" #include <bits/stdc++.h> #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #line 4 "datastructure/unionfind.hpp" struct unionfind { int n; std::vector<int> data; unionfind(int _n) : n(_n), data(_n, -1) { } int root(int x) { return (data[x] < 0) ? x : data[x] = root(data[x]); } bool unite(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) std::swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool find(int x, int y) { return root(x) == root(y); } int size(int x) { return -data[root(x)]; } std::vector<std::vector<int>> groups() { std::vector<int> root_buf(n), group_size(n); for (int i = 0; i < n; i++) { root_buf[i] = root(i); group_size[root_buf[i]]++; } std::vector<std::vector<int>> ret(n); for (int i = 0; i < n; i++) { ret[i].reserve(group_size[i]); } for (int i = 0; i < n; i++) { ret[root_buf[i]].push_back(i); } ret.erase(std::remove_if( ret.begin(), ret.end(), [&](const std::vector<int>& v) { return v.empty(); }), ret.end()); return ret; } }; #line 5 "test/library-checker/unionfind.test.cpp" int main() { int n, q; std::cin >> n >> q; unionfind uf(n); while (q--) { int t, u, v; std::cin >> t >> u >> v; if (t == 0) { uf.unite(u, v); } if (t == 1) { std::cout << int(uf.find(u, v)) << '\n'; } } }