等价关系：需要同时满足下列三个性质的关系R
1、自反性：对于所有的a属于集合S，a R a(自身与自身有关系)2、对称性：a R b当且仅当b R a(如果a和b有关系，则b和a也有关系)3、传递性：若a R b且b R c，则a R c(如果a和b有关系，b又和c有关系，则a和c有关系)等价集合：如果一个元素a 属于集合S，则元素a的等价集合是集合S的一个子集，它包含所有与元素a有等价关系的元素。
输入数据最初是N个元素（元素也是一个集合）的集合，其中每个集合只含有一个元素，且互不相同，也不存在等价关系，使得这些集合互不相交，此时只能进行两种运算：一种find操作，一种Union操作。
Find操作：返回包含给定元素的集合（等价集合）的名字
Union操作：首先先判断要进行此操作的两个元素是否已经在同一个等价集合中，若判断两个元素分别属于不同的等价集合，则把含有a 和 b的两个等价集合合并为一个新的等价集合
注意：该算法是动态的，因为在算法的执行过程中，集合可以通过Union操作而发生改变
基本数据结构：使用树（tree）来表示一个等价集合，一个颗树只有一个根节点，所以等价集合的名字由根处的节点给出，同一颗树上的节点具有共同的根节点，在执行find操作时，只要返回根节点信息即可。注意：这里指的树不一定是二叉树。由于只需要关心其父节点信息，所以我们就可以使用一个数组来表示这棵树，数组的每个成员P[i]表示元素 i 的父亲，如果 i 是根，那么P[i] = 0。
那么初始代码如下：
for（i = 1; i <= 8; i++）
S[ i ] = 0;//代表每个元素集合互不相交
Find操作代码如下：
int find(int i, int S[])
{
if（S [ i ] ==0）
return i;//返回此树的根
else
return find(S[i], S);//否则不断通过其父节点往上查找，直至找到根
}
Union（X, Y）约定为Y的根为X，Union操作代码如下：
void Union（int S[], int root1, int root2）
{
S [root2] = root1;
}
由于上面的合并是随机的，这样会存在一个问题：这颗树有时会退化为一个链表，导致find操作时间复杂度为O（n），因此我们需要按照一定的规则来进行合并：
按大小合并：使得总让较小的树成为较大的树的子树（根节点存储节点个数的负值，初始时为-1）
void Union（int S[], int root1, int root2）
{
int temp；
temp = S[root1] + S[root2];
if(S[root1] < S[root2])
{
S[root2] = root1;
S[root1] = temp;
}
else
{
S[root1] = root2;
S[root2] = temp;
}
}
按高度合并：使得高度小的树成为高度大的树的子树（根节点存储高度的负值，初始时为0）
void Union（int S[], int root1, int root2）
{
if(S[root1] < S[root2])
{
S[root2] = root1;
}
else
{
S[root1] = root2;
if(S[root1] == S[root2])
S[root2]--;
}
}
路径压缩：从X到根的路径上每一个节点，都使它们的父节点变成根
Find操作代码如下：
int find(int i, int S[])
{
if（S [ i ] <= 0）
return i;//返回此树的根
else
return S[i] = find(S[i], S);//更新寻找根路径上每一个节点的父节点为根
}
