#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A" #include <bits/stdc++.h> #include "../../Data-Structure/Disjoint-Set/union-find.hpp" using namespace std; int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); constexpr char LF = '\n'; int N, Q; cin >> N >> Q; UnionFind uf(N); while (Q--) { int com, x, y; cin >> com >> x >> y; if (com == 0) { uf.unite(x, y); } else { cout << uf.same(x, y) << LF; } } return 0; }
#line 1 "test/AOJ/DSL_1_A.test.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A" #include <bits/stdc++.h> #line 7 "Data-Structure/Disjoint-Set/union-find.hpp" /** * @brief Union-Find (素集合データ構造) * @note path-compression + union-by-size */ class UnionFind { private: int n; mutable std::vector<int> p; public: UnionFind() = default; explicit UnionFind(int n_) : n(n_) , p(n_, -1) {} int unite(int x, int y) { x = leader(x), y = leader(y); if (x == y) return x; if (p[y] < p[x]) std::swap(x, y); p[x] += p[y]; p[y] = x; return x; } int leader(int x) const { return p[x] < 0 ? x : p[x] = leader(p[x]); } bool same(int x, int y) const { return leader(x) == leader(y); } int size(int x) const { return -p[leader(x)]; } std::vector<std::vector<int>> groups() const { std::vector<int> leaderBuf(n), groupSize(n); for (int i = 0; i < n; i++) ++groupSize[leaderBuf[i] = leader(i)]; std::vector<std::vector<int>> result(n); for (int i = 0; i < n; i++) result[i].reserve(groupSize[i]); for (int i = 0; i < n; i++) result[leaderBuf[i]].push_back(i); result.erase(std::remove_if(result.begin(), result.end(), [](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } }; #line 5 "test/AOJ/DSL_1_A.test.cpp" using namespace std; int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); constexpr char LF = '\n'; int N, Q; cin >> N >> Q; UnionFind uf(N); while (Q--) { int com, x, y; cin >> com >> x >> y; if (com == 0) { uf.unite(x, y); } else { cout << uf.same(x, y) << LF; } } return 0; }