Submit Info #3688

Problem Lang User Status Time Memory
Unionfind cpp (anonymous) AC 52 ms 2.24 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
random_00 AC 36 ms 1.80 MiB
random_01 AC 43 ms 1.98 MiB
random_02 AC 31 ms 1.17 MiB
random_03 AC 9 ms 1.93 MiB
random_04 AC 24 ms 0.87 MiB
random_05 AC 40 ms 1.13 MiB
random_06 AC 32 ms 2.24 MiB
random_07 AC 6 ms 1.40 MiB
random_08 AC 13 ms 0.67 MiB
random_09 AC 52 ms 1.67 MiB

#include <bits/stdc++.h> using namespace std; struct dsu { vector<int> p, sz; dsu(int n) : p(n, -1), sz(n, 1) {} int root(int v) const { while (p[v] != -1) v = p[v]; return v; } bool unite(int u, int v) { u = root(u), v = root(v); if (u == v) return false; if (sz[u] < sz[v]) swap(u, v); p[v] = u; sz[u] += sz[v]; return true; } bool same(int u, int v) const { return root(u) == root(v); } int size(int v) const { return sz[root(v)]; } }; int main() { int n, q; scanf("%d%d", &n, &q); dsu d(n); while (q--) { int t, u, v; scanf("%d%d%d", &t, &u, &v); if (t == 0) { d.unite(u, v); } else { printf("%d\n", d.same(u, v)); } } }