互斥集主要用于Kruskal算法中，用于求圖的最小生成樹。
?
互斥集主要有3個基本操作：
?
1. 初始化各個集合
Make(a)p[a] ← a ?
?
2. 查找各個集合的老祖宗
Find(a)if a == p[a] : return aelse : return Find(p[a])
?
?
3.? 合并兩個集合
Union(a, b)p[Find(b)] ← Find(a) ?
?
上面是第一個版本，相對比較簡單；但是，這個版本在某些情況下存在效率低下的問題，例如在查找老祖宗的時候形成直線的連接。
解決這個問題有兩種方法：
1. 在find的過程中，將中間查找到的節點全部掛到最終查找到的祖宗節點下去。
2. 在union的時候每次總是將層次小的集合掛到層次大的集合下去。
rank[x]: level of set:xMake(x)p[x] ← xrank[x] ← 0
?
?
Find(x)IF x ≠ p[x] p[x] ← Find_Set(p[x])RETURN p[x] ?
?
Union(x, y)Link( Find_Set(x), Find_Set(y) ) ?
?
Link(x, y)IF rank[x] > rank[y]p[y] ← x ELSE p[x] ← yIF rank[x] == rank[y]rank[y]++
?
?
?
)
和Quartz集成詳解（四）)
![BZOJ1834 [ZJOI2010]network 網絡擴容](http://pic.xiahunao.cn/BZOJ1834 [ZJOI2010]network 網絡擴容)
)