Disjoint set

• 用於整理多個屬於同一類別的element

• 當一個element的root等於自身時，代表一顆tree

• 透過計算有幾顆tree即可得知有幾種資料分組

• set[element] = root

所需函式

• INIT(x)

準備總element數量(x)的陣列空間，並將其root設為自身

• UNION(x,y)

將x、y的root設為同一個

• FIND(x)

回傳x的root值

實作

UVA-10583 部份code

int stu[50000];

void Init(int n)
{
	int i;
	for(i = 0;i < n;i++) {
		stu[i] = i;
	}
}

int Find(int x)
{
	if(stu[x] == x) return x;
	else {
		stu[x] = Find(stu[x]);
		return stu[x];
	}
}

void Union(int a, int b)
{
	stu[Find(a)] = Find(b);
}

其中為了防止Find函式在element數量大時須做多次recursive減低效率

(在tree最大level過大時會發生此狀況)

在Find()中做了對tree「修剪」的動作(else部份)