This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Kyo-s-s/Library
#include <bits/stdc++.h> using namespace std; #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include "../Data_structure/UnionFind.hpp" int main() { int N, Q; cin >> N >> Q; UnionFind uf(N); while (Q--) { int t, u, v; cin >> t >> u >> v; if (t == 0) { uf.merge(u, v); } else { cout << (uf.same(u, v) ? 1 : 0) << endl; } } }
#line 1 "Test/yosupo-UnionFind.test.cpp" #include <bits/stdc++.h> using namespace std; #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #line 1 "Data_structure/UnionFind.hpp" struct UnionFind { int n, cnt; vector<int> parent; UnionFind() : n(0), cnt(0) {} UnionFind(int n) : n(n), cnt(n), parent(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < n && 0 <= b && b < n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent[x] < -parent[y]) swap(x, y); parent[x] += parent[y]; parent[y] = x; cnt--; return x; } int leader(int a) { assert(0 <= a && a < n); if (parent[a] < 0) return a; return parent[a] = leader(parent[a]); } bool same(int a, int b) { assert(0 <= a && a < n && 0 <= b && b < n); return leader(a) == leader(b); } int size(int a) { assert(0 <= a && a < n); return -parent[leader(a)]; } int count() { return cnt; } vector<vector<int>> groups() { vector<int> leader_buf(n), group_size(n); for (int i = 0; i < n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } vector<vector<int>> result(n); for (int i = 0; i < n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < n; i++) { result[leader_buf[i]].push_back(i); } result.erase( remove_if(result.begin(), result.end(), [&](const vector<int> &v) { return v.empty(); }), result.end()); return result; } }; #line 7 "Test/yosupo-UnionFind.test.cpp" int main() { int N, Q; cin >> N >> Q; UnionFind uf(N); while (Q--) { int t, u, v; cin >> t >> u >> v; if (t == 0) { uf.merge(u, v); } else { cout << (uf.same(u, v) ? 1 : 0) << endl; } } }