若集合X上的关系R是自反的，对称的和传递的，则称关系R是集合X上的等价关系，等价关系R说明（设R为定义在X上的二元关系）：
（1）自反：对于每个x∈X，都有（x，x）∈R；
（2）对称：对于任意的x，y∈X，若当（x，y）∈R时，有（y，x）∈R；
（3）传递：对于任意的x，y，z∈X，当（x，y）∈R且（y，z）∈R时，有（x，z）∈R。
等价关系的实质是将集合中的元素分类，按照R将集合X划分若干不相交的子集，则这些子集的集合为X的关于R的等价类。
用并查算法来确定等价类：
（1）令有n个元素的集合X中的每个元素各自构成一个只含单个元素的子集X1，X2...Xn；
（2）重复读入m个等价对（x，y），对于每个读入的等价对，设x∈Xi，y∈Xj，如果Xi=Xj，则不做任何操作；
若Xi≠Xj，则将Xj并入Xi中，并将Xj置空（或将Xi并入Xi中，并将Xj置空）。
算法执行完成后，所有的非空集合即为X的关于等价关系R的等价类。
等价类可以采用树结构表示，采用双亲结点表示法。将集合中元素放到数组中（包含数据域data和指针域parent），根据并查算法把归属于同一个集合的元素放到同一个根结点的树中。
代码实现如下（题例在注释里）：
package Tree; /** * @author sun * 创建时间：2017年5月5日下午2:37:23 */ //根据并查算法建立等价类 //设集合X={X|1<=x<=10,且x是整数，R是X上的等价关系} class ESetNode{//采用双亲表示法的结点类 int data; int parent; public ESetNode(){} } public class ESet {//集合（树）类 private ESetNode[] x; private int n;//元素个数 public ESet(int n){ //构造函数，初始时，每个元素自成一棵树 this.n = n; this.x = new ESetNode[n]; for(int e=1;e<n;e++){//为了使元素与下标一致方便调用 x[e] = new ESetNode();//单个元素自成树 x[e].data = e; x[e].parent = -1;//初始无父节点 } } int Find(int i){ //查函数返回包含结点i的树的根结点 int e = i; while(x[e].parent>=0) e = x[e].parent;//因为只有根结点parent为负数 return e; } void Union(int i,int j){ //并，将根为j的树并到根为i的树上 x[j].parent = i; int e = Find(i); x[e].parent = x[e].parent-1;//记录根为i的树的元素个数 } public static void main(String[] args) { final int n = 10; ESet e = new ESet(n+1); //等价关系R={(1,3),(3,5),(3,7),(2,4),(4,6),(2,8)} if(e.Find(1)!=e.Find(3)) e.Union(1, 3); if(e.Find(3)!=e.Find(5)) e.Union(3, 5); if(e.Find(3)!=e.Find(7)) e.Union(3, 7); if(e.Find(2)!=e.Find(4)) e.Union(2, 4); if(e.Find(4)!=e.Find(6)) e.Union(4, 6); if(e.Find(2)!=e.Find(8)) e.Union(2, 8); //输出 for(int i=1;i<=n;i++) System.out.print(e.x[i].data+" "+e.x[i].parent+"\n"); } } /* 1 -4 2 -4 3 1 4 2 5 3 6 4 7 3 8 2 9 -1 10 -1 */