test/aoj/DSL_1_A.test.cpp

View this file on GitHub
Last update: 2023-07-12 23:09:17+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"

#include "../../template/template.hpp"
#include "../../data_structure/unionfind.hpp"

int main() {
  int N, Q;
  cin>>N>>Q;
  UnionFind uf(N);
  REP(loop,Q) {
    int t, x, y;
    cin>>t>>x>>y;
    if (t == 0)
      uf.unite(x, y);
    else
      cout<<(uf.find(x) == uf.find(y))<<endl;
  }
}

#line 1 "test/aoj/DSL_1_A.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"

#line 2 "template/template.hpp"
// clang-format off
#include <bits/stdc++.h>
// #include <atcoder/all>
// #include <boost/multiprecision/cpp_int.hpp>
// #include <boost/multiprecision/integer.hpp>
typedef long long int ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,n) for(ll i=0;i<signed(n);i++)
#define EREP(i,n) for(ll i=1;i<=signed(n);i++)
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
// using namespace atcoder;
// using boost::multiprecision::cpp_int;
// namespace mp = boost::multiprecision;
//#define EVEL 1
#ifdef EVEL
#define DEB(X) cout << #X <<":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const ll INF = 9e18;
typedef std::pair<ll, ll> P;
struct edge { ll to, cost; };
#define VMAX 100000
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template <class T> T vgcd(T m, T n) {return std::gcd(m, n);}
template <class T, class... Args> T vgcd(T a, Args... args) {return vgcd(a, vgcd(args...));}
const long long MOD = 998244353;
// using mint = static_modint<998244353>;
// clang-format on
ll ans = 0;
bool F = false;
#line 2 "data_structure/unionfind.hpp"

struct UnionFind {
  vector< int > data;

  UnionFind() = default;

  explicit UnionFind(size_t sz) : data(sz, -1) {}

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return false;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if(data[k] < 0) return (k);
    return data[k] = find(data[k]);
  }

  int size(int k) {
    return -data[find(k)];
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  vector< vector< int > > groups() {
    int n = (int) data.size();
    vector< vector< int > > ret(n);
    for(int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(remove_if(begin(ret), end(ret), [&](const vector< int > &v) {
      return v.empty();
    }), end(ret));
    return ret;
  }
};
#line 5 "test/aoj/DSL_1_A.test.cpp"

int main() {
  int N, Q;
  cin>>N>>Q;
  UnionFind uf(N);
  REP(loop,Q) {
    int t, x, y;
    cin>>t>>x>>y;
    if (t == 0)
      uf.unite(x, y);
    else
      cout<<(uf.find(x) == uf.find(y))<<endl;
  }
}