Algorithm - Disjoint Set

Course

可以參考我做的課程簡報：

MST & Shortest Path

Disjoint Set 並查集

一棵樹代表一個集合，樹根為最高祖先
原先每個樹皆為獨立，一棵樹只有一個節點
透過不斷尋找根結點 (父親) 來將樹逐漸合併
最終成為一棵完整的樹

Disjoint Set

Find update Parent

int find(int x){
	if(parent[x] < 0) return x;
	return parent[x] = find(parent[x]);
}

Union Subtrees

int find(int x){
	if(parent[x] < 0) return x;
	return parent[x] = find(parent[x]);
}

void Union(int a, int b){
	a = find(a);
	b = find(b);

	if(a != b){
		if(parent[a] < parent[b]){
			parent[a] += parent[b];
			parent[b] = a;
		}
		else{
			parent[b] += parent[a];
			parent[a] = b;
		}
	}
}

UVA Problem

UVA 00908 - Re-connecting Computer Sites