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

• View this file on GitHub
• Last update: 2023-02-22 09:23:56-08:00
• Include: #include "union-find/union-find.hpp"

概要

素集合データ構造です
詳しくはググってください

例

• UnionFind(int N) := N頂点のUniFを作る $O(N)$
• int find(int x) := 頂点xの親を探す $O(α)$
• void unite(int x, int y) := 頂点xと頂点yを辺でつなげる $O(α)$
• int size(int x) := 頂点xが属する木のサイズを返す $O(α)$
• bool same(int x, int y) := 頂点xと頂点yが同じ木に含まれているか判定する $O(α)$
• vector<int> members(int x) := 頂点xと同じ木に含まれている頂点を全て返す $O(αN)$
• vector<int> roots() := 親を全て返す $O(αN)$
• int grp_cnt() := 木の数を返す $O(1)$
• unordered_map<int,vector<int>> grp_mem() := 親をkey、その木に含まれているすべての頂点のリストをvalueとしたunordered_mapを返す $O(αN)$

Verified with

• verify/yosupo/union-find.test.cpp

Code

#include<iostream>
#include<vector>
#include<unordered_map>
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 1 "union-find/union-find.hpp"
#include<iostream>
#include<vector>
#include<unordered_map>
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;
    }
};

Back to top page