Submit Info #2594

Problem Lang User Status Time Memory
Unionfind cpp satanic0258 AC 218 ms 2.17 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.62 MiB
random_00 AC 169 ms 1.75 MiB
random_01 AC 171 ms 1.88 MiB
random_02 AC 134 ms 1.08 MiB
random_03 AC 35 ms 1.84 MiB
random_04 AC 111 ms 0.78 MiB
random_05 AC 154 ms 1.18 MiB
random_06 AC 130 ms 2.17 MiB
random_07 AC 19 ms 1.37 MiB
random_08 AC 59 ms 0.74 MiB
random_09 AC 218 ms 1.55 MiB

#line 1 "test/yosupo/unionfind.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include <bits/stdc++.h> #line 1 "test/yosupo/../../data-structure/UnionFind.cpp" class UnionFind { private: std::vector<int> par; std::vector<int> siz; public: UnionFind(int sz_) : par(sz_), siz(sz_, 1) { for (int i = 0; i < sz_; ++i) par[i] = i; } void init(int sz_) { par.resize(sz_); siz.resize(sz_, 1); for (int i = 0; i < sz_; ++i) par[i] = i; } int find(int x) { while (par[x] != x) x = par[x] = par[par[x]]; return x; } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (siz[x] < siz[y]) std::swap(x, y); siz[x] += siz[y]; par[y] = x; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return siz[find(x)]; } }; #line 6 "test/yosupo/unionfind.test.cpp" #define REP(a,b) for(int a=0;a<(int)(b);++a) signed main(){ int n, q; std::cin >> n >> q; UnionFind uf(n); REP(i, q) { int t, u, v; std::cin >> t >> u >> v; /* */if (t == 0) uf.unite(u, v); else if (t == 1) std::cout << uf.same(u, v) << "\n"; } return 0; }