并查集原理与实现

并查集原理

（1）并查集用于解决以下问题

用于处理没有重复元素的集合(不交集)的查询和合并。可以快速判断一个元素是否在一个集合中，或者两个元素是否属于同一个集合。

（2）并查集支持以下操作：

查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
合并：将两个集合合并为一个。
添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。

（3）并查集使用数组实现

初始时并查集由一系列孤立的元素组成，如图所示：

例如给出以下集合：1，3，5，7，8，用并查集表示如下：

1下标对应 3，3下标对应5，5下标对应7，7下标对应8，8 对应8，这样该集合的代表元素是 8，下面用 8 来表示这个集合。1，3，5，7，8就用并查集表示出来了。

通过使用并查集，我们可以判断某个元素是否属于 8 这个集合，例如 5 这个元素，5 下标对应 7，7 下标对应 8，8 对应 8（结束）这样就知道 5 属于 8 这个集合。
使用并查集也可以快速判断某些元素是否属于同一个集合，例如 3，5，下标 3 对应 5，下标 5 对应 7，下标 7 对应 8，下标 8 对应 8（结束），再来看 5，下标 5 对应 7，下标 7 对应 8，下标 8 对应 8（结束）。使用同样的查找方式，我们都找到 3 和 5 都能对应8，说明 3 和 5 都属于同一个集合。

并查集是一种树形数据结构，上述讨论的集合用树来表示如下：

每个节点只有一个孩子节点，此时这棵树构成了一个单链表，查询效率也是最低的。查询元素 1 时需要查询 5 次。为了提高查询效率，需要对并查集进行路径压缩，如下图所示：

此时为查询效率是最高的，查询任何一个元素都能在 2 次比较后结束。

并查集的常用操作

初始化

1	vector<int>fa(n+1);

使用fa 来表示并查集，它的元素范围从 1 到 n。刚开始，fa 只是一系列孤立的元素值。

1 2	for(int i=1;i<=n;++i) fa[i]=i;

查找

以下用 c++ 语言实现

int find(int x){
    if(fa[x]==x)
        return x;
    else
        return find(fa,fa[x]);
}

合并

两集合合并是指将其中一个集合的代表元素指向另一个集合的代表元素，反之也可以。如下图所示：

如上图所示，合并有两种方案，很面向左边的方案树的深度更低，查询更高效，右边的方案不好，因为它的深度更高，查询效率更低。

为了总是按照第一种方案来合并，我们就必须采用按秩合并（启发式合并）。使用一个数组来记录集合的深度，让深度大的集合合并深度小的集合。具体代码如下：

vector<int>size(n+1,1);       // 初始化所有元素的深度为 1

int unite(int x, int y)
{
    int xx = find(x);
    int yy = find(y);
    if(xx==yy)
        return;
    
  	// 保证小的合并到大的
    if(size[xx]>size[yy]){
        fa[yy] = xx;
        size[xx] += size[yy];     // 跟踪深度大小
    }else{
        fa[xx] = yy;
        size[yy] += size[xx];    
    }    
}

时间复杂度

使用路径压缩和启发式合并后，并查集的每个操作都能在 O(α(n))，n 表示元素个数，α 表示阿克曼反函数，其增长极其缓慢，其单次操作的平均运行时间可以认为是一个很小的常数，对于一般可能出现的数值n，α(n)均小于5。

阿克曼函数定义如下：n 为元素个数， m 为运算次数。

如果只使用启发式合并，而不使用路径压缩，时间复杂度为 O(m log n)，

如果只使用路径压缩，而不使用启发式合并，时间复杂度为 O(m α(m,n))

有时将 α(m,n) 写作 α(n)，将 m 看作一个常数。

空间复杂度

取决于元素个数，即 O(n)

参考

https://oi-wiki.org/ds/dsu/#_5

阿克曼函数 - 维基百科，自由的百科全书

并查集 - 维基百科，自由的百科全书

编程之禅

并查集原理与实现