Union Find
作成日：2019.01.17
最終更新日：2019.01.17
目次
実装
テンプレート引数
T_size
要素の個数(の最大値)
変数
int p[T_size]
集合の代表である要素では負で集合に含まれる要素の個数の$-1$倍を、そうでない要素では非負で親の要素番号をもつ
int uni_count
併合が起きた回数をもつ(関数uniが呼ばれた回数ではない)
パブリック関数
int boss(int a)
$a$を含む集合の代表となる要素を返す
void uni(int a, int b)
$a$を含む集合と$b$を含む集合を併合する(両者が同じ時は何もしない)
bool find(int a, int b)
$a,b$が同じ集合に含まれているかを判定する
int count()
併合が起きた回数を返す(要素の個数からこれを引けば、現在の集合の個数が求まる)
int member(int a)
$a$を含む集合に属する要素の数を返す
ソースコード
template <int T_size> class Union_Find{
int p[T_size];
int uni_count;
public:
Union_Find(){
std::fill(p,p+T_size,-1);
uni_count = 0;
}
int boss(int a){
return p[a] >= 0 ? p[a]=boss(p[a]) : a;
}
void uni(int a , int b){
int s = boss(a);
int t = boss(b);
if(s != t){
++uni_count;
if(p[s] > p[t]) std::swap(s,t);
p[s] += p[t];
p[t] = s;
}
}
bool find(int a , int b){
return boss(a) == boss(b);
}
int count(){
return uni_count;
}
int member(int a){
return -p[boss(a)];
}
};注意点
このコードでは要素の番号は0-indexedであるが、そのままで1-indexedとしても使える。
(これは実装上の注意だが)"union"は共用体の宣言に用いられるキーワードなので、関数名としては使えない。