#include <cstdio> //{{{ #include <iostream> #include <vector> #include <string> #include <set> #include <map> #include <algorithm> #define ALL(c) (c).begin(), (c).end() #define DUMP(x) std::cerr << #x << ':' << x << '\n'; typedef long long ll; // clang-format off template<typename T,typename U>inline bool chmax(T&x,U a){if(x>=a)return 0;x=a;return 1;} template<typename T,typename U>inline bool chmin(T&x,U a){if(x<=a)return 0;x=a;return 1;} inline int in(){int x;scanf("%d", &x);return x;} // clang-format on // }}} //{{{ uf.hpp #ifndef INCLUDE_UF_HPP #define INCLUDE_UF_HPP #include <vector> #include <algorithm> namespace orliv { //{{{ UF merge, same, root, size, count struct UF { std::vector<int> data; int cnt; UF(int n) : data(n, -1), cnt(n) {} bool merge(int a, int b) { a = root(a); b = root(b); if (a != b) { cnt--; if (data[b] < data[a]) std::swap(a, b); data[a] += data[b]; data[b] = a; } return a != b; } bool same(int a, int b) { return root(a) == root(b); } int root(int a) { return data[a] >= 0 ? data[a] = root(data[a]) : a; } int size(int a) { return -data[root(a)]; } int count() { return cnt; } }; //}}} //{{{ UF2d merge, same, size, count struct UF2d { UF uf; const int W, H; UF2d(int w, int h) : uf(w * h), W(w), H(h) {} bool merge(int ax, int ay, int bx, int by) { return uf.merge(ay * W + ax, by * W + bx); } bool same(int ax, int ay, int bx, int by) { return uf.same(ay * W + ax, by * W + bx); } int size(int x, int y) { return uf.size(y * W + x); } int root(int x, int y) { return uf.root(y * W + x); } int count() { return uf.count(); } }; //}}} } #endif //}}} using namespace std; int main() { int N = in(), Q = in(); orliv::UF uf(N + 1); for (; Q--;) { int a = in(), b = in(), c = in(); if (a) puts(uf.same(b, c) ? "YES" : "NO"); else uf.merge(b, c); } return 0; }
Note that non-ascii characters in the above source code will be escaped (such as \x9f).