:heavy_check_mark: dsu/test/union_find.test.cpp

Depends on

Code

#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;
        }
    }
}
Back to top page