Union Find

作成日:2019.01.17
最終更新日:2019.01.17

目次

  1. 概要
  2. 原理
  3. 計算量
  4. 実装

実装

テンプレート引数

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"は共用体の宣言に用いられるキーワードなので、関数名としては使えない。

目次に戻る

広告

自己紹介

プログラミングとかUTAUとかドット絵とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告