sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include "../../data-structure/unionfind/union_find.hpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, Q; cin >> N >> Q; UnionFind uf(N); for (int i = 0; i < Q; i++) { int t, u, v; cin >> t >> u >> v; if (t == 0) uf.unite(u, v); else cout << uf.same(u, v) << "\n"; } }
#line 1 "test/yosupo/unionfind.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #line 2 "data-structure/unionfind/union_find.hpp" #include <algorithm> #include <vector> class UnionFind { public: UnionFind() = default; explicit UnionFind(int n) : data(n, -1) {} int find(int x) { if (data[x] < 0) return x; return data[x] = find(data[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (data[x] > data[y]) std::swap(x, y); data[x] += data[y]; data[y] = x; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -data[find(x)]; } private: std::vector<int> data; }; #line 4 "test/yosupo/unionfind.test.cpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, Q; cin >> N >> Q; UnionFind uf(N); for (int i = 0; i < Q; i++) { int t, u, v; cin >> t >> u >> v; if (t == 0) uf.unite(u, v); else cout << uf.same(u, v) << "\n"; } }