Submission #420552

---

Source Code Expand

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <tuple>
#include <stack>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
 
#include <vector>

class UnionFind{
 private:
  std::vector<int> p_gs_; //正なら親ノードの番号で負なら自身がルートで値は-groupsize
  int groups_;            //groupの数

 public:
  const int nodes;        //ノードの数

  UnionFind(int size):p_gs_(size, -1),nodes(size),groups_(size){}

  bool unite(int x, int y){
    int rx = root(x), ry = root(y);
    if(rx!=ry){
      --groups_;
      if(p_gs_[ry] < p_gs_[rx]) std::swap(rx, ry); //rx<ryにしてrxにryを連結
      p_gs_[rx] += p_gs_[ry];
      p_gs_[ry] = rx;
    }
    return rx != ry;
  }

  bool same(int x, int y){ return root(x)==root(y); }
  int root(int x){ return p_gs_[x]<0 ? x : p_gs_[x]=root(p_gs_[x]); }
  int gsize(int x){ return -p_gs_[root(x)]; }
  int groups() const{ return groups_; }
};  
 
using namespace std;
int main(int, char** ){
    cin.tie(nullptr); ios::sync_with_stdio(false);

    int n,q;
    cin >> n >> q;
    int p,a,b;
    UnionFind uf(n);
    for(int i = 0; i < q; ++i){
        cin >> p >> a >> b;
        if(p==0){
            uf.unite(a,b);
        }else{
            if(uf.same(a,b)){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
    }

    return 0;
}

Submission Info

Judge Result