不相交集类

动态等价性问题

给定一个等价关系 ~ ，一个自然的问题是对任意的 $a$ 和 $b$，确定是否$a~b$。如果将等价关系存储为布尔变量的一个二维数组，那么当然这个工作可以以常数时间完成。问题在于，关系通常不是明显而是相当隐秘地定义的。

一个元素$a \in S$ 的等价类时 $S$ 的一个子集，它包含所有与 $a$ 有等价关系的元素。注意。等价类形成对 $S$ 的一个划分： $S$的每一个成员恰好出现在一个等价类中。为确定是否$a~b$，我们只需验证 $a$ 和 $b$ 是否都在同一个等价类中。这给我们提供了解决等价问题的方法。

输入数据最初是 $N$ 个集合的类，每个集合含有一个元素。初始的描述是所有的关系均为 $false$（自反除外）。每个集合都有一个不同的元素，从而 $S_i \cap S_j = \emptyset$；这使得这些集合不相交

此时有两种操作允许进行。第一种操作是 find ，它返回包含给定元素的集合名字。第二种操作是添加关系。如果我们想要添加关系 $a~b$，那么我们首先要看$a$和$b$是否已经有关系。这可以通过对$a$和$b$执行$find$并检验它们是否在同一个等价类中来完成。如果它们不再同一个等价类中，那么我们使用求并操作 Union ，将它们合并成一个新的等价类。从集合观点看，就是去掉两个集合生成一个新集合而保持所有集合的不相交性。常常把这项工作的算法叫做不相交集合的 union/find 算法

而由于等价类会通过 find 和 union 操作动态的更新，所以该算法是动态的，并且它还是一种联机操作

解决动态等价性问题的数据结构

一种想法是用树来表示每一个等价类，因为树上的每一个元素都有相同的根。这样，该根就可以用来命名所在的等价类。而用树的集合（森林）来表示整个集合（被划分为多个等价类）

我们可以假设树被非显示存储在一个数组中：数组的每个元素 $S[i]$ 表示元素 $i$ 的父亲，如果 $i$ 是根，那么 $S[i] = -1$

初始化时，将所有的元素赋值为 $-1$ 即 $S[i] = -1(0 \leq i < n)$

动态等价性有两种关键操作

find() 用于查找元素所在的等价类
union() 用于将两个元素分别所处的等价类合并成一个等价类

而每种操作都有相应的实现算法，它们将决定解决动态等价性问题的运行时间。
下面是对两种操作的介绍

find 操作

简单的算法
因为 $S[i]$ 表示元素 $i$ 的父亲，所以在使用 $find(x)$ 时可以直接递归$find()$来找到节点 $x$ 的根节点，用它的位置来表示节点 $x$ 所在的等价类的名字
但它的弊端在于他的运行时间，因为有可能建立一颗深度为$N-1$的树（使用union操作的第一种算法），所以它的最坏运行时间为 $O(N)$，在这种情况下连续执行 $M$ 次操作的最坏运行时间为 $O(MN)$
路径压缩算法
$find(x)$ 操作会让从节点 $x$ 到根节点的每一个节点都成为根节点的子节点（通过更新 $S[i]$ 来实现）
当出现深层节点较多的情形时，业以证明，连续 M 次运行最多需要 $O(M \log N)$ 的时间(即使是使用union操作的第一种算法)

union 操作

下面三种算法大同小异，相同之处在于当执行 union 操作时，都是通过使一颗树的根的父链链接到另一个树的根节点来实现合并，例如两个等价类 $a,b$ 他们的根分别处于数组的$i,j$位置，如果将等价类$b$合并到等价类$a$，那么更新等价类 $b$ 的根节点上的值$S[j] = i$
而这三种算法的不同之处在于树的根节点的含义以及如何更新另一个树的根节点

简单的算法
即不考虑两个等价类的大小，而直接将第二个等价类并入到第一个等价类中，此时根节点 $S[i]$ 任就是 $-1$
其缺点在于会使 $find$ 操作的最坏运行时间为 $O(N)$
基于等价类大小的合并算法
在该算法中根节点$S[i]$值为该等价类所含元素数量的相反数
在合并时考虑两个等价类中所含元素的多少，将含有元素少的等价类并入到含有元素多的等价类中，同时更新该等价类 根节点 中所存储的值为 现在该等价类所含元素数量的相反数，更新好后的根节点 $S[i] = S[i] + S[j]$ (这里的$S[j]$表示等价类$b$未被并入等价类$a$时根节点的值)

因为节点的深度最多可以增加 $\log N$ 所以此时 $find$ 操作的最坏运行时间为 $O(\log N)$,连续执行 $M$ 次操作的最坏运行时间为 $O(M\log N)$，对于真正所有合理的模型，业以证明，连续执行 $M$ 次操作的平均时间为 $O(M)$。这是因为当随机的诸 union 操作执行时整个算法只有一些很小的集合与大集合合并
基于等价类高度的合并算法
在该算法中根节点$S[i]$值为该等价类的高度的相反数 - 1
在合并时考虑两个等价类的高度，将高度小的等价类并入到高度大的等价类中，同时更新该等价类 根节点 中所存储的值 $S[i]$
- 若两个等价类高度不同，那么 $S[i]$ 不变
- 若两个等价类高度相同，那么 $S[i] = S[i] - 1$
  
  因为节点的深度最多可以增加 $\log N$ 所以此时 $find$ 操作的最坏运行时间为 $O(\log N)$,连续执行 $M$ 次操作的最坏运行时间为 $O(M\log N)$，对于真正所有合理的模型，业以证明，连续执行 $M$ 次操作的平均时间为 $O(M)$
  
  下图第一行为按大小合并的数组结果，第二行为按高度合并的数组结果

find 操作与 union 操作的组合

由于实现 find 操作和实现 union 操作都有不同的算法。所以组合他们也是很关键的。
find 中的路径压缩算法和 union 操作中的基于等价类大小的合并算法是完全兼容的。
find 中的路径压缩算法和 Union 操作中的基于等价类高度的合并算法不是完全兼容的，因为路径压缩可以改变等价类的高度，其 $M$ 次 union 和 find 的运行时间为 $O(M \log ^* N)$

一个应用——迷宫的生成

首先生成 N 个等价类（一个有 N 个点）
如果相让两点连通（即让两点等价），则使用 union 操作
当起点与终点连通时，迷宫生成完毕

代码实现

Code

package equivalence;

public class Equivalence {
    private int[] tree;

    //路径压缩算法
    public int find(int x) {
        if (tree[x] <= -1) {
            return x;
        }
        return tree[x] = find(tree[x]);
    }

    //根据等价类大小合并
    public void union(int equivalenceRoot1, int equivalenceRoot2) {
        if (tree[equivalenceRoot1] < tree[equivalenceRoot2]) {
            tree[equivalenceRoot1] += tree[equivalenceRoot2];
            tree[equivalenceRoot2] = equivalenceRoot1;
        } else {
            tree[equivalenceRoot2] += tree[equivalenceRoot1];
            tree[equivalenceRoot1] = equivalenceRoot2;
        }
    }

    Equivalence(int size) {
        tree = new int[size];
        for (int i = 0; i < size; i++) {
            tree[i] = -1;
        }
    }

    public static void main(String[] args) {
        Equivalence equivalence = new Equivalence(10);
        System.out.println(equivalence.find(1) == equivalence.find(2));
        equivalence.union(1,2);
        System.out.println(equivalence.find(1) == equivalence.find(2));
    }
}