Code Festival B Union Find by

#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).

download

return to the top page