不相交集合

如果两个集合没有公共元素，则称它们为不相交集合。并集（或并查集）数据结构用于跟踪固定数量的元素，这些元素被划分为若干个不相交的集合。

Disjoint sets 类有两个方法：

1. connect(int p, int q)：把两个元素合并起来，成为一个。
2. isConnected(int p, int q)：判断两个元素是否属于同一个并集。

接下来我们讲四种实现方式：

快速查找

connect 方法要首先在 List 中遍历，查找 p 和 q，这样会很慢: O(n)。因此我们先用快速查找优化一下查找方法。

我们规定：建立一个数组，数组的下标对应指定的数字，而数组对应的值是这个数字所属的集合编号。

这样规定之后，connect 方法就是把下标对应的值改成集合编号，而 isConnected 方法则是判断两个下标对应的值是否相等。这样做到的时间复杂度为 O(1)；

快速联合

这一部分主要是让几个集合连接在一起，成为一个集合。这里还是用数组实现。

我们假想一个集合是一颗树，集合的根对应的数字，其值为-1；剩下的数字的值，是父节点的数字。

此外我们还需要定义一个 find 函数，来查找某个数字对应的集合的根是谁。

这样规定之后，connect 方法就是把使得 find(p) = find(q) ，而 isConnected 方法则是判断 find(p) == find(q)。这样做到的时间复杂度为 O (1)；

加权快速联合（WQU）