相关概念
等价关系
若对于每一对元素(a, b), ，aRb或者为true或者为false，则称在集合S上定义关
系（relation)R。如果aRb是true，则说a与b有关系。
等价关系（equivalence relation）是满足下列三个性质的关系R:
1.（自反性）对于所有的，aRa。
2.（对称性）aRb当且仅当bRa。
3.（传递性）若aRb且bRc，则aRc。
比如<=不是等价关系，电气连通性是一个等价关系
等价类
一个元素的等价类是S的一个子集，它包含所有与a有等价关系的元素。
为确定是否aRb，我们只需验证a和b是否都在同一个等价类中。
不相交集合的find/union算法
对于该等价类，一般有两种操作。
- find
它返回包含给定元素的集合（即等价类）的名字 - union
用于添加关系aRb
具体步骤：
- 首先检查a和b是否在同一个等价类中
- 如果不在，则使用union操作，将含有a和b的两个等价类合并成一个新的合并类
注：现已证明两个操作不能同时以常数最坏情形运行时间执行。
基本数据结构
使用树表示每一个集合，根用来命名所在的集合。
// Process Init
public DisjSets(int numElements) {
s = new int[numElments];
for(int i=0; i<s.length; i++)
s[i] = -1;
}
// Process Union
public void union(int root1, int root2) {
s[root2] = root1;
}
// Process Find
public int find(int x) {
if(s[x]<0)
return x;
else
return find(s[x]);
}
平均情形分析依赖于如何定义平均（对于union操作涉及大树的概率）。由于union操作随机，因此最坏情况下会让树高呈线性增长。
按大小求并
对于union操作，总让较小的树成为较大的树的子树。
那么任何节点的深度均不会超过logN
实现
让每个根的数组元素包含它的树的大小的负值，则不需要额外的空间。
按高度求并
跟踪每棵树的高度，对于union操作，使得浅的树成为深的树的子树。
同样保证所有的树的深度最多是logN
实现
让每个根的数组元素包含它的树的高度的负值-1，则不需要额外的空间
已证明，若使用按大小/高度求并，则连续M次运算（union/find）需要O(M)平均时间，但O(MlogN)的最坏情况还是可能相当容易和自然发生的。
路径压缩
对于find(x)操作，从x到根的路径上的每一个节点都使其指向该树的根。
public int find(int x) {
if(s[x]<0)
return x;
else
return s[x] = find(s[x]);
}
路径压缩与按大小求并兼容，而不完全与按高度求并兼容（路径压缩可以改变树的高度）。针对于按高度求并，我们不重新计算高度，而将其作为秩，成为按秩求并。
已证明，对于两种求并方法（按大小求并/按秩求并），路径压缩都能够显著地减少最坏情况运行时间。
应用
生成迷宫
