并查集以及一些变种

Published: by Creative Commons Licence

  • Tags:

并查集

提个问题

存在若干个元素,$e_1,e_2,\ldots,e_n$。要求我们支持两种操作:

1.对于给定$i$与$j$,将$e_i$,$e_j$所在的两个集合合并为一个。

2.对于给定$i$与$j$,判断$e_i$,$e_j$是否处于同一个集合中

如果你将这些元素视作顶点,那么操作1实际是建立边$(e_i, e_j)$,而操作2是询问顶点$e_i$与顶点$e_j$是否连通。问题就转换为图论问题。

并查集是专门用于解决这两个问题的数据结构。

按秩合并

并查集的最简单的实现方式是维护一个森林。为每个元素建立一个结点,每个结点维护两个属性:father和rank。father表示父结点,而rank是以自己为根的子树的大小。

class Node{
    Node father = this;
    int rank = 1;
    public Node getRoot(){
        return father == this ? father : father.getRoot();
    }
}

查询操作的结果可以通过判断两个元素所在树的根是否相同得到。

合并操作使用的是启发式合并,合并之前先找到两个结点所在树的根,并通过判断根是否相同判断两元素是否处于相同的集合中,如果是相同集合,就可以跳过合并。否则,则将较小集合的根的father字段设置为较大集合的根,并更新较大集合的根的rank字段。

Node union(Node a, Node b){
    a = a.getRoot();
    b = b.getRoot();
    if(a == b){
        return a;
    }
    if(a.rank >= b.rank){
        b.father = a;
        a.rank += b.rank;
        return a;
    }else{
        a.father = b;
        b.rank += a.rank;
        return b;
    }
}

由于这里使用的是启发式合并,每次只有较小的树会合并到较大的树中。而一个结点$u$与根的距离每扩大1,意味着它作为较小树中的成员合并到了较大的树中,而$u$所在的树的大小至少增大了一倍。由于$u$所在的树的大小最大为$n$,因此最多被合并$\log_2n$次,即$u$与根的距离最大为$\log_2n$。

因此查询和合并的时间复杂度均为$O(\log_2n)$。

路径压缩

可以看到按秩合并的主要时间费用都花在了getRoot()方法上,这个方法的时间复杂度为$O(\log_2n)$。那么我们能不能想个法子优化这个方法呢。

路径压缩就是一个好方法。首先father仅用来查询根结点,因此我们可以设置father为任何距离根结点更近的祖先结点,这样就可以减少每次查询花费的时间。其次需要重新定义秩,在按秩合并的情况下,秩代表的是子树的大小,但是在路径压缩技巧中,秩代表的是树的高度。

class Node{
    Node father;
	int rank;
    public Node getRoot(){
        return father.father == father ? father : (father = father.getRoot());
    }
}
Node union(Node a, Node b){
    a = a.getRoot();
    b = b.getRoot();
    if(a == b){
        return a;
    }
    if(a.rank == b.rank){
        a.rank++;
    }
    if(a.rank > b.rank){
        b.father = a;
        return a;
    }else{
        a.father = b;
        return b;
    }
}

这里getRoot()的时间复杂度会低于$O(\log_2n)$,事实上,你可以认为在你可以想象的任意大数据集中,它都是$O(1)$,这里并不给出证明,可以自行参考《算法导论》。

持久化

假如我们在原始的问题中再加上一个操作:

3.允许我们将并查集切换回到之前的某个版本。

这个问题就有点难度了。由于操作2是读操作,而操作1仅会修改两个结点的状态。因此假如我们用持久化结构保存每个结点的信息(father和rank),这样就可以同时实现版本的切换了。

但是注意如果我们使用路径压缩的技巧,可能一次操作会修改很多的结点(尽管摊还是$O(1)$),这就不适合使用持久化了。因此我们选择的优化技巧是按秩合并。

持久化结构可以使用持久化线段树或者持久化无旋Treap,它们的读写操作时间复杂度都为$O(\log_2n)$。因此在使用持久化结构作为底层的情况下,操作1、2的时间复杂度均为$O((\log_2n)^2)$,而操作3的时间复杂度为$O(1)$。

一类平面三点生成问题

如果平面上存在三个顶点$(r_1,c_1)$和$(r_1,c_2)$和$(r_2,c_1)$,那么就会自动生成$(r_2,c_2)$。同时新生成的顶点也会加入到生成流程中来。直到不能再生成新的顶点流程才结束。

问题1:给定一个$n\cdot m$矩形,矩形的每个单元中仅包含0和1,如果某个矩形的三个角落都是1,那么剩下的角落也会被自动修改成1,这个流程直到不能生成新的顶点位置。现在已知这样一个01矩阵,问至少需要将多少个0修改成1,才能保证每个位置在流程结束的时候都是1。

这是一个经典的并查集问题。我们可以为每一行每一列都建立一个对应顶点,这样总共有$n+m$个顶点。

之后如果某个位置$(x,y)$初始为1,那么就将行$x$代表的顶点和列$y$代表的顶点合并。

可以发现,如果一个顶点$(a,b)$存在(为1),那么一定满足$a$行和$b$列处于同一个连通块。

同时现在考虑如果对于一个顶点$(r_2,c_2)$如果被生成,那么就意味着存在三个位置$(r_1,c_1),(r_1,c_2),(r_2,c_1)$,这时候行$r_2$和列$c_2$是处于相同连通块的。

因此我们得出了一个顶点存在的充分必要提交,一个顶点存在,当且仅当其所在行和列的顶点在相同连通块。

因此问题是问,我们需要加入多少边才能使得所有连通块连通,答案自然是连通块数目减1。

提供一道CF题目