版本 1ddc54e06dbfbd0858dd19bafc25e14de39e0cf3
Changes from 1ddc54e06dbfbd0858dd19bafc25e14de39e0cf3 to 0141f915e6744f08276608d35bf34b87ff29e320
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
```c
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部份)
