【并查集的启发式合并】

在并查集执行合并操作 Union()，将两个集合合并为一个时，无论将哪一个集合连接到另一集合的下面都是正确的，但不同的连接方法存在时间复杂度的差异

具体来说，如果将一棵结点数、深度都较小的集合树，连接到一棵更大的集合树下，显然相比于另一种连接方案，在接下来执行查找操作 Find() 时，时间复杂度会更小

但不能总是恰好遇到结点数、深度都小的集合，鉴于结点数、深度这两个特征都较容易维护，常常选择其中的一个来作为估价函数，来进行合并评估

在Tarjan的论文[1]中，证明了无论选择哪一种作为估价函数，时间复杂度都是

$$O(m\alpha(m,n))$$

这就是并查集的启发式合并优化，又称为并查集的按秩合并

【实现】

下面给出选择结点数作为估计函数的实现方法

int father[N];
vector<int> size(N, 1);    //记录并初始化子树的大小为1
void Union(int x, int y) { //以结点数为估计函数的启发式合并
    int fx = Find(x); //x的根结点
    int fy = find(y); //y的根结点
    if (fx == fy)     //x、y属于同一集合的根结点
        return;
    if (size[fx] > size[fy]) // 保证小的集合合并到大的集合
        swap(fx, fy);
    father[fx] = fy;      //合并
    size[fy] += size[fx]; //维护结点数
}

Reference

[1]Gabow, H. N., & Tarjan, R. E. (1985). A Linear-Time Algorithm for a Special Case of Disjoint Set Union. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 30, 209-221.CORE PDF