test/aoj/DSL_1_A.test.cpp

• View this file on GitHub
• Last update: 2022-03-13 15:34:49+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

Depends on

• Union Find Tree (Disjoint Set Union) (graph/UnionFind.cpp)

Code

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

#include <bits/stdc++.h>
#ifdef __LOCAL
#define DBG(X) cout << #X << " = " << (X) << endl;
#define SAY(X) cout << (X) << endl;
#else
#define DBG(X)
#define SAY(X)
#define NDEBUG
#endif

using namespace std;

typedef int_fast32_t int32;
typedef int_fast64_t int64;

const int32 inf = 1e9+7;
const int32 MOD = 1000000007;
const int64 llinf = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define all(obj) (obj).begin(),(obj).end()
#define rall(obj) (obj).rbegin(),(obj).rend()
#define fi first
#define se second
#define pb(a) push_back(a)
typedef pair<int32,int32> pii;
typedef pair<int64,int64> pll;

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) { a = b; return true; } return false;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) { a = b; return true; } return false;
}

#include "../../graph/UnionFind.cpp"

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n,q;
  cin >> n >> q;
  UnionFind uf(n);
  while(q--){
    int com,x,y;
    cin >> com >> x >> y;
    if(com == 0){
      uf.unite(x,y);
    }else{
      ANS(uf.same(x,y));
    }
  }
  return 0;
}

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

#include <bits/stdc++.h>
#ifdef __LOCAL
#define DBG(X) cout << #X << " = " << (X) << endl;
#define SAY(X) cout << (X) << endl;
#else
#define DBG(X)
#define SAY(X)
#define NDEBUG
#endif

using namespace std;

typedef int_fast32_t int32;
typedef int_fast64_t int64;

const int32 inf = 1e9+7;
const int32 MOD = 1000000007;
const int64 llinf = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define all(obj) (obj).begin(),(obj).end()
#define rall(obj) (obj).rbegin(),(obj).rend()
#define fi first
#define se second
#define pb(a) push_back(a)
typedef pair<int32,int32> pii;
typedef pair<int64,int64> pll;

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) { a = b; return true; } return false;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) { a = b; return true; } return false;
}

#line 2 "graph/UnionFind.cpp"
using namespace std;

/**
 * @brief Union Find Tree (Disjoint Set Union)
 */
struct UnionFind{
  /**
   * @brief n頂点0辺のグラフで初期化する.
   * @details O(n)
   * 
   * @param n 頂点数
   */
  UnionFind(int n){
    par = vector<int>(n, -1);
    connectedComponentCnt = n;
  }

  /**
   * @brief 辺(x,y)を追加する.
   * @details O(\alpha(n)) amortized
   * 
   * @param x 
   * @param y 
   * @return true 頂点x, yはもともと別の連結成分にあり, 連結成分のマージが行われた.
   * @return false 頂点x, yはもともと同じ連結成分にあり, 連結成分のマージは行われなかった.
   */
  bool unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x == y)return false;
    if(-par[x] < -par[y])swap(x,y);
    par[x] += par[y];
    par[y] = x;
    --connectedComponentCnt;
    return true;
  }

  /**
   * @brief 頂点x, yが同じ連結成分に属しているかどうか調べる.
   * @details O(\alpha(n)) amortized
   * 
   * @param x 
   * @param y 
   * @return 
   */
  bool same(int x, int y){
    return root(x) == root(y);
  }

  /**
   * @brief 頂点xを含む連結成分の頂点数を返す.
   * @details O(\alpha(n)) amortizedW
   * 
   * @param x 
   * @return int 
   */
  int size(int x){
    return -par[root(x)];
  }

private:
  vector<int> par;
  int connectedComponentCnt;
  int root(int x){
    if(par[x] < 0)return x;
    return par[x] = root(par[x]);
  }
};
#line 45 "test/aoj/DSL_1_A.test.cpp"

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n,q;
  cin >> n >> q;
  UnionFind uf(n);
  while(q--){
    int com,x,y;
    cin >> com >> x >> y;
    if(com == 0){
      uf.unite(x,y);
    }else{
      ANS(uf.same(x,y));
    }
  }
  return 0;
}

Back to top page