并查集

定義

并查集是一種維護集合的資料結構，支援以下兩種操作：

1. 合并：合并兩個集合。
2. 查找：判斷兩個元素是否在一個集合。

對同一個集合來說隻存在一個根結點，且将其作為所屬集合的辨別。

基本操作

初始化

一開始，每個元素都是獨立的集合，是以令所有father[i]=i。

for(int i=0; i<n; i++) {
	father[i]=i;
}
           

查找（路徑壓縮）

反複地尋找元素的父親節點，在查找的過程中把路徑上所有的結點父親都指向根結點。

int findFather(int x) {
	//因為x要被覆寫，是以保留一個副本
	int a=x;
	while(x!=father[x]) {
		x=father[x];
	}
	while(a!=father[a]) {
		//因為a要被覆寫，是以保留一個副本
		int z=a;
		father[z]=x;
		a=father[a];
	}
	return x;
}
           

合并

1. 對于給定的兩個元素a、b，判斷它們是否屬于同一集合。
2. 合并兩個集合：在第一步中已經獲得了兩個元素的根結點faA和faB，是以隻需要根據需求把其中一個的父節點指向另一個。

void Union(int a,int b) {
	int faA=findFather(a);
	int faB=findFather(b);
	if(faA!=faB) {
		father[faA]=faB;
	}
}