This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include <bits/extc++.h> using namespace std; #include "../dsu.hpp" signed main() { int n, q; cin >> n >> q; dsu uf(n); while (q--) { int t, x, y; cin >> t >> x >> y; if (t) cout << uf.same(x, y) << '\n'; else uf.merge(x, y); } }
#line 1 "data-structure/test/Unionfind.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include <bits/extc++.h> using namespace std; #line 1 "data-structure/dsu.hpp" struct dsu { public: dsu(int n) : n(n), p(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < n); assert(0 <= b && b < n); int x = head(a), y = head(b); if (x == y) return x; if (-p[x] < -p[y]) swap(x, y); p[x] += p[y]; p[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < n); assert(0 <= b && b < n); return head(a) == head(b); } int head(int a) { assert(0 <= a && a < n); if (p[a] < 0) return a; return p[a] = head(p[a]); } int size(int a) { assert(0 <= a && a < n); return -p[head(a)]; } vector<vector<int>> groups() { vector<int> tmp(n), sz(n); for (int i = 0; i < n; ++i) tmp[i] = head(i), ++sz[tmp[i]]; vector<vector<int>> gr(n); for (int i = 0; i < n; ++i) gr[i].reserve(sz[i]); for (int i = 0; i < n; ++i) gr[tmp[i]].push_back(i); gr.erase(remove_if(begin(gr), end(gr), [&](const vector<int>& v) { return v.empty(); }), end(gr)); return gr; } private: int n; vector<int> p; }; #line 8 "data-structure/test/Unionfind.test.cpp" signed main() { int n, q; cin >> n >> q; dsu uf(n); while (q--) { int t, x, y; cin >> t >> x >> y; if (t) cout << uf.same(x, y) << '\n'; else uf.merge(x, y); } }