Union-Find

Union-Find とは

　素集合データ構造を扱うアルゴリズム。

　つまり、グループ分けを扱える。ただし、1 つの要素が複数のグループに属することはない。

Union-Find のアルゴリズム

　Union-Find には、主に Union と Find の 2 つの操作がある。

• Union(x,y)
• 要素 x を含むグループと要素 y を含むグループを統合する。x と y が同じグループなら何もしない。

• Find(x)
• 要素 x を含むグループの値 (例えば、グループの代表の要素) を返す。

 実装方法

　高速に Union-Find を行うには、それぞれのグループを木とした素集合森でデータを扱うとよい。それぞれ、木の根をグループの代表者とみなす。初期状態において、各要素は自分のみのグループに属する。

Union と Find それぞれを工夫することで高速化を図る。Union は Find を用い、それ以外の部分は \(O(1)\) であるため、Union と Find の計算量は同じである。

Union

　2 つの木の高さまたは要素数を比較し、小さいほうの根を大きいほうの根に連結する。どちらか好きなほうを実装すればよい。

どちらを用いても、Union または Find の計算量は、\(O(\log n)\)。

　また、Find の高速化で木の高さが減少することがあるため、Find の高速化と併用すると正確な木の高さは取得できなくなることに注意。要素数は変わらないため、取得できるようにしておくといいことがあるかも (競プロで使うことはある)。

Find

　Find の計算量は木の高さ (Find する要素と根の距離) に依存する。そのため、Find しながら木の高さを減らしていく。以下の 3 つのうち好きなものを実装すればよい。

・path compression

　[Find する要素] の親を新たな要素とする。これを要素が根になるまで続ける。根まで到達したら、辿ったすべての要素の親を根に書き換える。

・path splitting

　[Find する要素の親, 要素の親の親] を新たな [要素, 要素の親] とする。これを要素が根になるまで続ける。

・path halving

　Find する要素の親を要素の親の親に書き換える。その後、要素の親 (元は親の親) を新たな要素とする。これを要素が根になるまで続ける。つまり、path splitting は、[元: 親] を新たな要素とするのに対し、path halving は、[元: 親の親] を新たな要素とする。

どれを用いても、Union または Find の計算量は、\(O(\log n)\)。

　Union と Find の高速化を併用すると、Union または Find の計算量は、ならし \(O(\alpha (n))\) (\(\alpha\) はアッカーマン関数の逆関数で、ほぼ \(O(1)\))。

結局ソースコードは？ (C++)

　まず、コンストラクタを用いて、親 p を以下のように初期化する。

// vector<int> p;

// p[i]>=0 の場合、p[i] は p の親
// p[i]<0 の場合、p は根で、
// 　高さ (rank) を扱う場合、
// 　　根の高さを 1 とするなら、rank==-p[i]
// 　　根の高さを 0 とするなら、rank==~p[i]
// 　要素数を扱う場合、size==-p[i]

UnionFind(int n):p(n,-1){}  // n はグループ分けしたい要素の数

このようにすることで、親と [高さまたは要素数] を 1 つの配列で扱える。

Union

　高さや要素数は負で扱っているので、比較するときに不等号が逆になることに注意。また、union は C++ の予約語なので、関数名は、unite にしてあることにも注意。

・高さ (rank)

void unite(int x, int y){  // 要素 x を含む木 (以下 x の木) と要素 y を含む木 (以下 y の木) を統合する
	x=find(x);y=find(y);  // x の木の根、y の木の根を取得
	if(x==y)return;  // 根が同じ (= グループが同じ) なら何もしない
	
	if(p[x]==p[y]){  // 高さが同じなら
		++p[x];  // x の木の高さを 1 増やす
		p[y]=x;  // y の木の根を x の木の根に連結する
	}
	else if(p[x]<p[y]){  // x の木のほうが高いなら
		p[y]=x;  // y の木の根を x の木の根に連結する
	}
	else{  // y の木のほうが高いなら
		p[x]=y;  // x の木の根を y の木の根に連結する
	}
	return;
}

・要素数 (size)

void unite(int x, int y){  // 要素 x を含む木 (以下 x の木) と要素 y を含む木 (以下 y の木) を統合する
	x=find(x);y=find(y);  // x の木の根、y の木の根を取得
	if(x==y)return;  // 根が同じ (= グループが同じ) なら何もしない
	
	if(p[x]<p[y]){  // x の木のほうが要素数が多いなら
		p[x]+=p[y];  // x の木の要素数に y の木の要素数をたす
		p[y]=x;  // y の木の根を x の木の根に連結する
	}
	else{  // y の木のほうが要素数が多いなら
		p[y]+=p[x];  // y の木の要素数に x の木の要素数をたす
		p[x]=y;  // x の木の根を y の木の根に連結する
	}
	return;
}

Find

・path compression

int find(int x){  // 要素 x を含む木 (以下 x の木) の根を返す
	if(p[x]<0)return x;  // x が根なら x を返す
	int root=x;  // root を x で初期化
	while(p[root]>=0){  // root が根になるまで
		root=p[root];  // root の親を新たな root とする
	}

	int parent;
	while(p[x]!=root){  // x の親が root になるまで
		parent=p[x];  // x の親を保持
		p[x]=root;  // x の親を root に書き換える
		x=parent;  // [元: x の親] を新たな x とする
	}
	return root;
}

・path splitting

int find(int x){  // 要素 x を含む木 (以下 x の木) の根を返す
	if(p[x]<0)return x;  // x が根なら x を返す
	while(p[p[x]]>=0){  // x の親が根になるまで
		tie(x,p[x])={p[x],p[p[x]]};  // [x の親, x の親の親] を新たな [x, x の親] とする
	}
	return p[x];
}

・path halving

int find(int x){  // 要素 x を含む木 (以下 x の木) の根を返す
	if(p[x]<0)return x;  // x が根なら x を返す
	while(p[p[x]]>=0){  // x の親が根になるまで
		p[x]=p[p[x]];  // x の親を x の親の親 に書き換える
		x=p[x];  // x の親 (元: x の親の親) を新たな x とする
		if(p[x]<0)return x;  // x が根なら x を返す
	}
	return p[x];
}

まとめると

　Union を 要素数 (size)、Find を path halving にした場合。(別の手法を用いたい場合は、適宜、unite と find の部分を書き換えて下さい。)

どの関数も、ならし\(O(\alpha(n))\)

class UnionFind{
	vector<int> p;

	// p[i]>=0 の場合、p[i] は p の親
	// p[i]<0 の場合、p は根で、
	// 　高さ (rank) を扱う場合、
	// 　　根の高さを 1 とするなら、rank==-p[i]
	// 　　根の高さを 0 とするなら、rank==~p[i]
	// 　要素数を扱う場合、size==-p[i]

public:
	UnionFind(int n):p(n,-1){}  // n はグループ分けしたい要素の数
	
	void unite(int x, int y){  // 要素 x を含む木 (以下 x の木) と要素 y を含む木 (以下 y の木) を統合する
		x=find(x);y=find(y);  // x の木の根、y の木の根を取得
		if(x==y)return;  // 根が同じ (= グループが同じ) なら何もしない
		
		if(p[x]<p[y]){  // x の木のほうが要素数が多いなら
			p[x]+=p[y];  // x の木の要素数に y の木の要素数をたす
			p[y]=x;  // y の木の根を x の木の根に連結する
		}
		else{  // y の木のほうが要素数が多いなら
			p[y]+=p[x];  // y の木の要素数に x の木の要素数をたす
			p[x]=y;  // x の木の根を y の木の根に連結する
		}
		return;
	}
	
	int find(int x){  // 要素 x を含む木 (以下 x の木) の根を返す
		if(p[x]<0)return x;  // x が根なら x を返す
		while(p[p[x]]>=0){  // x の親が根になるまで
			p[x]=p[p[x]];  // x の親を x の親の親 に書き換える
			x=p[x];  // x の親 (元: x の親の親) を新たな x とする
			if(p[x]<0)return x;  // x が根なら x を返す
		}
		return p[x];
	}
	
	bool isSame(int x, int y){  // 要素 x と要素 y が同じグループなら true 違うなら false を返す
		return find(x)==find(y);
	}

	int size(int x){  // (要素数を扱う場合、) x を含むグループの要素数を返す
		return -p[find(x)];
	}
};

isSame 関数は、同じグループかどうか判断する関数です。size 関数は、(unite 関数を要素数 (size) にした場合のみ、) 要素数を取得できる関数です。

終わり！