#define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include<bits/stdc++.h> using namespace std; #include "../union_find.hpp" int main(){ int n,q; cin>>n>>q; UF uf(n); for(int i=0;i<q;++i){ int c,s,t; cin>>c>>s>>t; if(c==0){ uf.unite(s,t); }else{ cout<<uf.same(s,t)<<endl; } } }
#line 1 "dsu/test/union_find.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include<bits/stdc++.h> using namespace std; #line 1 "dsu/union_find.hpp" /** * @brief Union Find * @see https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0 */ class UF{ public: vector<int> data; int sz; public: UF(int sz):sz(sz){data.resize(sz,-1);} bool unite(int x,int y){ x=root(x);y=root(y); if(x==y)return 0; if(data[x]>data[y])swap(x,y); data[x]+=data[y]; data[y]=x; sz--; return 1; } inline int root(int x){return data[x]<0?x:data[x]=root(data[x]);} inline bool same(int x, int y){return root(x)==root(y);} inline int size(){return sz;} inline int size(int x){return -data[root(x)];} }; #line 5 "dsu/test/union_find.test.cpp" int main(){ int n,q; cin>>n>>q; UF uf(n); for(int i=0;i<q;++i){ int c,s,t; cin>>c>>s>>t; if(c==0){ uf.unite(s,t); }else{ cout<<uf.same(s,t)<<endl; } } }