并查集

DestinHistoire · 2019-08-03 18:59:14 · 个人记录

并查集

并查集(Disjoint-Set)是一种可以动态维护若干个不重叠的集合,并支持合并与查询的数据结构。详细地说,并查集包括如下两个基本操作:
1.get，查询一个元素属于哪一个集合。
2.merge，把两个集合合并成一个大集合。
为了具体实现并查集这种数据结构,我们首先需要定义集合的表示方法。在并查集中,我们采用“代表元”法,即为每个集合选择一个固定的元素,作为整个集合的“代表”。
其次,我们需要定义归属关系的表示方法。第一种思路是维护一个数组 fa ，用 fa 保存元素 x 所在集合的“代表”。这种方法可以快速查询元素的归属集合,但在合并时需要修改大量元素的 fa 值，效率很低。第二种思路是使用一棵树形结构存储每个集合，树上的每个节点都是一个元素，树根是集合的代表元素。整个并查集实际上是一个森林(若干棵树)。我们仍然可以维护一个数组 fa 来记录这个森林,用 fa[x] 保存 x 的父节点。特别地,令树根的 fa 值为它自己。这样一来,在合并两个集合时,只需连接两个树根(令其中一个树根为另一个树根的子节点,即 fa[root_1]=root_2)。不过在查询元素的归属时,需要从该元素开始通过 fa 存储的值不断递归访问父节点,直至到达树根。为了提高查询效率,并查集引入了路径压缩与按秩合并两种思想。

路径压缩与按秩合并

第一种思路(直接用数组 fa 保存代表)的查询效率很高，我们不妨考虑把两种思路进行结合。实际上,我们只关心每个集合对应的“树形结构”的根结点是什么，并不关心这棵树的具体形态——这意味着下图中的两棵树是等价的：
因此，我们可以在每次执行 get 操作的同时,把访问过的每个节点(也就是所查询元素的全部祖先)都直接指向树根，即把上图中左边那棵树变成右边那棵。这种优化方法被称为路径压缩，采用路径压缩优化的并查集，每次 get 操作的均摊复杂度为 O(log\ N)。
还有一种优化方法被杯为按秩合井。所谓“秩”，一般有两种定义。有的资料把并杏集中集合的“秩”定义为树的深度(未路径压缩时)。有的资料把集合的“秩”定义为集合的大小。无论采取哪种定义，我们都可以把集合的“秩”记录在“代表元素”，也就是树根上。在合并时都把“秩”较小的树根作为“秩”较大的树根的子节点。
值得一提的是,当“秩”定义为集合的大小时,“按秩合并”也称为“启发式合并”,它是数据结构相关问题中一种重要的思想,应用非常广泛,不只局限于并查集中。启发式合并的原则是：把“小的结构”合并到“大的结构”中，并且只增加“小的结构”的查询代价。这样一来，把所有结构全部合并起来，增加的总代价不会超过(N\ log\ M)。故单独采用“按秩合并”优化的并查集，每次 get 操作的均摊时间复杂度也是 O(log\ N)。

1.并查集的存储

使用一个数组 fa 保存父结点（根的父节点设为自己）。

int fa[SIZE];

2.并查集的初始化

设有 n 个元素，起初所有元素各自构成一个独立的集合，即有 n 棵 1 个点的树。

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

3.并查集的 get 操作

若 x 是树根，则 x 就是集合代表，否则递归访问 fa[x] 直至根节点。

int get(int x)
{
    if(x==fa[x])
        return x;
    return fa[x]=get(fa[x]);//路径压缩,fa 直接赋值为代表元素
}

4.并查集的 merge 操作

合并元素 x 和元素 y 所在的集合，等价于让 x 的树根作为 y 的树根的子节点。

void merge(int x,int y)
{
    fa[get(x)]=get(y);
}

“扩展域”与“边带权”的并查集

并查集实际上是由若干棵树构成的森林，我们可以在树中的每条边上记录一个权值即维护一个数组 d，用 d[x] 保存节点 x 到父节点 fa[x] 之间的边权。在每次路径压缩后，每个访问过的节点都会直接指向树根，如果我们同时更新这些节点的 d 值，就可以利用路径压缩过程来统计每个节点到树根之间的路径上的一些信息。这就是所谓“边带权”的并查集。

【例题】银河英雄传说(NOI2002/CH4101)

有一个划分成N列的星际战场,各列依次编号为 1,2,···,N。有 N 艘战舰，也依次编号为 1,2,···,N，其中第 i 号战舰处于第 i 列。
有M条指令,每条指令格式为以下两种之一:
1.M\ i\ j，表示让第 i 号战舰所在列的全部战舰保持原有顺序,接在第 j 号战舰所在列的尾部。
2.C\ i\ j，表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
N≤30000，M≤5* 10^5。

【分析】

一条“链”也是一棵树，只不过是树的特殊形态。因此可以把每一列战舰看作一个集合，用并查集维护。最初，N 个战舰构成 N 个独立的集合。
在没有路径压缩的情况下，fa[x] 就表示排在第 x 号战舰前面的那个战舰的编号一个集合的代表就是位于最前边的战舰。另外，让树上每条边带权值 1 ，这样树上两点之间的距离减 1 就是二者之间间隔的战舰数量。
在考虑路径压缩的情况下，我们额外建立一个数组 d，d[x] 记录战舰 x 与 fa 之间的边的权值。在路径压缩把x 直接指向树根的同时,我们把d[x] 更新为从 x 到树根的路径上的所有边权之和。下面的代码对 get 函数稍加修改,即可实现对 d 数组的维护：

int get(int x)
{
    if(x==fa[x])
        return x;
    int root=get(fa[x]);//递归计算集合代表
    d[x]+=d[fa[x]];//维护 d 数组——对边权求和
    return fa[x]=root;//路径压缩
}

当接收到一个 C\ x\ y 指令时，分别执行 get(x) 和 get(y) 完成查询和路径压缩。若二者的返回值相同，则说明 x 和 y 处于同一列中。因为 x 和 y 此时都已经指向树根，所以 d[x] 保存了位于 x 之前的战舰数量， d[y] 保存了位于 y 之前的战舰数量。二者之差的绝对值再减 1，就是 x 和 y 之间间隔的战舰数量。
当接收到一个 M\ x\ y 指令时,把 x 的树根作为 y 的树根的子节点，连接的新边的权值应该设为合并之前集合 y 的大小（根据题意，集合y 中的全部战舰都排在集合 x 之前)。因此，我们还需要一个 size 数组在每个树根上记录集合大小。下面这段对 merge 函数稍加修改的代码实现了这条指令：

void merge(int x,int y)
{
    x=get(x),y=get(y);
    fa[x]=y,d[x]=size[y];
    size[y]+= size[x];
}

并查集

并查集