test/aoj/DSL_1_A.quickfind.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 19:32:25+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

Depends on

• datastructure/quickfind.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../datastructure/quickfind.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,q;
  cin>>n>>q;
  QuickFind qf(n);
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c==0) qf.unite(x,y);
    if(c==1) cout<<qf.same(x,y)<<"\n";
  }
  cout<<flush;
  return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "datastructure/quickfind.cpp"

#line 3 "datastructure/quickfind.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct QuickFind{
  vector<int> rs,ps;
  vector< vector<int> > vs;
  QuickFind(int n):rs(n,1),ps(n),vs(n){
    iota(ps.begin(),ps.end(),0);
    for(int i=0;i<n;i++) vs[i].assign(1,i);
  }
  int find(int x) const{return ps[x];}
  bool same(int x,int y) const{
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=ps[x];y=ps[y];
    if(x==y) return;
    if(rs[x]<rs[y]) swap(x,y);
    rs[x]+=rs[y];
    for(int e:vs[y]){
      ps[e]=x;
      vs[x].emplace_back(e);
    }
    vs[y].clear();
    vs[y].shrink_to_fit();
  }
  const vector<int>& elements(int x) const{return vs[x];}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/DSL_1_A.quickfind.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,q;
  cin>>n>>q;
  QuickFind qf(n);
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c==0) qf.unite(x,y);
    if(c==1) cout<<qf.same(x,y)<<"\n";
  }
  cout<<flush;
  return 0;
}

Back to top page