verify/yosupo/union-find.test.cpp

• View this file on GitHub
• Last update: 2023-03-19 13:07:39-07:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Union Find (union-find/union-find.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

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

#include "../../union-find/union-find.hpp"

int main(){
    int n,q;
    cin>>n>>q;

    UnionFind uf(n);
    
    for(int _i=0;_i<q;_i++){
        int t,u,v;
        cin>>t>>u>>v;
        if(t==0){
            uf.unite(u,v);
        }else{
            cout<<(uf.same(u,v)?1:0)<<endl;
        }
    }
}

#line 1 "verify/yosupo/union-find.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

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

#line 4 "union-find/union-find.hpp"
struct UnionFind{
    int n;
    std::vector<int> par;
    int group_cnt;
    
    //要素数NのUnionFindを作成
    UnionFind(int n):par(n,-1),group_cnt(n),n(n){}

    //xの親を探す
    int find(int x){
        if(par.at(x)<0){
            return x;
        }else{
            par.at(x)=find(par.at(x));
            return par.at(x);
        }
    }

    //xとyを連結
    void unite(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        if(par.at(x)>par.at(y))std::swap(x,y);
        par.at(x)+=par.at(y);
        par.at(y)=x;
        group_cnt--;
        return;
    }

    int size(int x){
        return -par.at(find(x));
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }

    std::vector<int> members(int x){
        int root=find(x);
        std::vector<int> ret;
        for(int i=0;i<n;i++){
            if(find(i)==root)ret.push_back(i);
        }
        return ret;
    }

    std::vector<int> roots(){
        std::vector<int> ret;
        for(int i=0;i<n;i++){
            if(par.at(i)<0)ret.push_back(i);
        }
        return ret;
    }

    int grp_cnt(){
        return group_cnt;
    }

    std::unordered_map<int,std::vector<int>> grp_mem(){
        std::unordered_map<int,std::vector<int>> ret;
        for(int i=0;i<n;i++){
            ret[find(i)].push_back(i);
        }
        return ret;
    }
};
#line 7 "verify/yosupo/union-find.test.cpp"

int main(){
    int n,q;
    cin>>n>>q;

    UnionFind uf(n);
    
    for(int _i=0;_i<q;_i++){
        int t,u,v;
        cin>>t>>u>>v;
        if(t==0){
            uf.unite(u,v);
        }else{
            cout<<(uf.same(u,v)?1:0)<<endl;
        }
    }
}

Back to top page