君子反道以修德；正德以出乐；和乐以成顺。

# 并查集

并查集 (disjoint-set) 是用来判断两个元素是否位于同一集合的数据结构。采用数组进行具体实现，元素间的存储结构为树。并查集的基本操作包括查找和合并。

# 实现

# 查找操作

查找操作的作用是找到顶点所在树的根节点。

int find(int k){

    if (k == parent[k]) return k;

    return find(parent[k]);

}

由于递归占用空间较大，于是可以写成非递归的版本：

int find(int k){

    while(k != parent[k]) k = parent[k];

    return k;

}

# 合并操作

合并的作用是将两个顶点所在的集合合并为同一集合。

int merge(int u, int v){

    return find(u) = find(v);

}

显然，此时的查找和合并操作的时间复杂度均为 $O(h)$, 其中 $h$ 为树的高度。

注意到，在合并过程中，树的高度会每次增加 $1$, 进而最坏达到 $O(n)$ 的级别，于是让查找和合并的效率极大变低。于是，我们需要将树的高度进行压缩。

# 合并操作的优化

# 基于 size 的优化

我们可以将所含元素更少的集合并入所含元素较多的集合，以达到降低树的高度的目的。

int merge(int u, int v){

    int uRoot = find(u), vRoot = find(v);

    if(size[uRoot] > size[vRoot]){

        size[uRoot] += size[vRoot];

        return parent[vRoot] = uRoot;

    }

    else{

        size[vRoot] += size[uRoot];

        return parent[uRoot] = vRoot;

    }

}

此时，合并操作的复杂度为$O(h)$，但合并操作将树的高度$h$ 限制为$\log n$ 级别。于是查找和合并操作的最坏复杂度限制为$O(\log n)$ 级别。

# 基于 rank 的优化

注意到，size 不能完全反映树的高度关系。于是我们可以直接定义树的高度，将高度较小的数合并至高度较大的树中，从而不增加树的高度。我们采用一个数组 rank 记录树的高度。

int merge(int u, int v){

    int uRoot = find(u), vRoot  = find(v);

    rank[uRoot] > rank[vRoot] ? parent[vRoot] = uRoot : parent[uRoot] = vRoot;

    if (rank[uRoot] == rank[vRoot]) rank[vRoot]++;

    return parent[uRoot];

}

此时，树的高度$h$ 限制为$\log n$ 级别，于是查找和合并操作的最坏复杂度限制为$O(\log n)$ 级别。

# 查找操作的优化

对于查找操作，我们可以把经过路径的每一个节点都放到根节点上，从而使后续的查找更加方便，这样的操作称为路径压缩操作 (path compression)。代码实现是容易的：

int find(int k){

    if (k == parent[k]) return k;

    return parent[k] = find(parent[k]);

}

此时的复杂度仍为$O(h)$。注意到，如果写成这种形式，会让每次查找操作对应的$k$ 的 parent 的 parent 变成$k$ 的 parent 的 ancestor，于是最终除最初的节点以外，查找路径上的其余节点都连接到了根节点上，而最初的结点则连接在了其 parent 上。我们可以根据此进行优化。

非递归时，如果希望将查找的复杂度控制在$O(h)$ 级别，那么难以实现将所有顶点一次放到根节点之下。但是 Tarjan 和 Van Leeuwen 发明了路径减半算法，在一次复杂度为$O(n)$ 的查找后可以使树的深度变为原先的一半。具体代码如下：

int find(int k){

    if (k == parent[k]) return k;

    while(k != parent[k]){

        parent[k] = parent[parent[k]];

        k = parent[k];

    }

    return k;

}

此时的操作复杂度是略慢的 $O(h)$, 但多次查找后会明显加快速度。

# 说明

值得说明的是，为什么在查找操作中不需要维护 rank。实际上，在带有路径减半的查找过程中，树高的变化是比较复杂的。而且 rank 的作用本身就是提供一个序关系以优化合并过程，如不进行维护，同样可以提供一个在绝大多数情况下正确的序关系，而且减少维护的时间消耗。这样更为方便快捷。这也是 rank 不叫做 height 或 depth 的原因。

# 并查集的最终复杂度

根据上面的复杂度分析，对查找次数较少的情况，复杂度为$m\log n$。

实际上，在多次查找和合并的情况下，均摊复杂度为 $O(m\log^*n)$, 其中

$$\log^*n := \left\{\begin{matrix}0,&\text{if}\; n \leq 1\\ 1+\log^*(\log n), & \text{otherwise} \end{matrix}\right.$$

是函数的反函数，一般意义下的值 (不超过 $2^{65536}$ ) 不超过 $5$, 可以视为常数。