「强制在线」动态图连通性(的LCT实现)

「强制在线」动态图连通性(的LCT实现)

昨天学习了一下动态图连通性,并且打了个板子。别人的板子好像大多数都是基于ETT的,然而我比较菜不会ETT,只好用LCT来实现。

Holm-de Lichtenberg-Thorup 算法

某个课件

官方题解

这个算法的大致思想是维护图的一个生成森林,同时维护非树边。在树边被切断时,我们需要判断有没有非树边能够代替被删掉的边,并且如果有的话需要找到一条这样的边把它变成树边。为了高效地实现这一过程,需要赋予每条边一个等级来表示它的局部度:等级高的边更有可能连接图上比较“接近”的点,而等级低的边连接的范围可能会更广泛一些。边的等级并不代表它实际上的局部程度,而只是我们在算法中对它的局部程度的一个估计,并且随时可能会被修改。

在算法的执行过程中,始终有以下两条性质:

  1. 维护的生成森林是关于等级的最大生成森林
  2. 等级至少为kk的边形成的每个连通块大小不超过n2k\frac{n}{2^k}

在加入一条边时,先设它的等级为00。如果它合并了原来的两个连通块,我们就把它加入树边中,否则我们就先不管它。

在删除一条边时,假设当前它的等级为kk,我们想要找一条非树边来代替它。为了保持性质1,也为了检查尽量少的边(我们猜测这条边附近的边更有可能能够替换删掉的边),我们从kk00依次检查每个等级是否有可以代替它的边。(由性质1一定没有等级更高的边能代替它)。下面考虑检查是否有等级为aa的边能代替刚刚删掉的这条边的函数 Reconnect(a):

设删掉的这条边的两个端点分别是u,vu,v。删掉这条边后,uuvv就不再连通了。我们需要检查原图的生成森林中边权至少是aa的子森林中uuvv的连通块里的所有非树边,判断是否有一条能代替删掉的边。为了检查尽量少的边,我们需要检查uuvv所在的边权至少是aa的连通块中比较小的那个。不妨设uu所在的连通块比较小。

注意到一个端点在uu中的非树边只有两种可能:第二个端点要么在uu中,要么在vv中。如果它的两个端点都在uu中,那我们就认为这条边局部性比较强,把它的等级增加11。否则我们就找到了一条可以用来替代的边。但是这样有个问题:非树边的等级被增加后,原来的最大生成森林可能就不再是最大生成森林了。为了保持这一性质,我们需要在检查uu连通块的非树边之前先把uu连通块里的树边的等级都加11

由于原来的连通块满足性质2,我们增加树边的等级后得到的新连通块大小不超过原来的一半,所以我们得到的新连通块也满足性质2。

由于每条边的等级最多被提升logn\log n次,每提升一次等级需要logn\log n的时间,这个算法的时间复杂度为O(nlog2n)O(n \log ^2 n)

实现细节

为了让以上复杂度分析得以成立,我们需要通过数据结构在O(logn)O(\log n)的时间内高效地维护以下信息:

  1. 连通块的大小
  2. 找到连通块中任意一个等级为kk的树边
  3. 找到连通块中任意一个等级为kk的非树边

这些信息都是可以用LCT维护的,虽然我们需要维护轻边的信息。我们对每个等级维护一棵LCT,在每条树边上建立一个虚点,在等级为kk的LCT的每个节点上维护等级至少是kk的树边,并且记录

  1. 当前splay中它的子树及子树的点的轻儿子的点数和
  2. 轻儿子的点数和
  3. 当前splay中它的子树及子树的点的轻儿子中有没有等级为kk的树边
  4. 有等级为kk的树边的轻儿子列表
  5. 当前splay中它的子树及子树的点的轻儿子中有没有等级为kk的非树边
  6. 有等级为kk的非树边的轻儿子列表
  7. 以这个点为端点的非树边列表

以上所有“列表”为了插入删除方便全都可以用unordered_map实现。

可以发现,这些信息足够我们找到以某个点为根的连通块内的非树边或树边。需要注意的是,在找到一条边之后需要把它access一下来保证复杂度。在实现修改操作时,比较好写的一种方案是把它evert成根以后直接修改。

需要注意在rotate的时候,如果被旋转点的父亲是某条链顶上的节点,需要维护它的父亲的父亲的轻儿子信息。

生成数据

一种比较强的生成数据的方法是如果当前图里的边数超过nn就让插入的概率小于删除的概率,否则就让插入的概率大于删除的概率,保证图里有nn条左右的边,这样询问的结果会比较均匀。

发表评论

电子邮件地址不会被公开。 必填项已用*标注