浅谈连通性

· · 个人记录

本文会讨论各种连通性的问题，以及他们的内在联系。 连通性问题，绝大多数是围着双中心围点打援：tarjan和最小生成树。

tarjan主要处理的是无边权的问题，而最小生成树解决的是一类有边权的贪心连通性问题。

基于最短路的连通性问题，只要想到传递闭包或者最短路树在上面解决问题基本上就解决了，不详细叙述。

最后还会提一类特殊的连通性问题。

tarjan:

强联通&双连通分量，分别对应有向图和为无向图的连通性。

给出一个 N 个点 M 条边的有向图，求有多少对 (i,j) 满足 i 可以走到 j ?

用tarjan缩点是tarjan的经典应用，缩完点后拓扑排序dp即可。

SDOI2010所驼门王的宝藏：三种门，第一种能到同行的点，第二种能到同列的点，第三种能到周围八个各自的点，问最多经过多少点。

这个连通性问题非常特殊，我们可以对每行建立一条边，对每列建立一条边，对于每种门点向对应的行和列连边，tarjan跑缩点，dp计算答案。

SDOI2018战略游戏：你需要删掉最少的点使得两点不连通，多组询问。

我们知道删掉点不连通这个东西就是割点，但是不能每次跑一遍。 所以我们需要用tarjan建出圆方树，由于有 k 个点， 我们可以建出圆方树的虚树，问题就转化为统计虚树路径上非询问的圆点的数量。

最小生成树：

(写在前面，永远不要觉得最小生成树是 $log$ 的，他是可以做到几乎线性的，非常强大)

最小生成树，本质上是一种贪心：

最短路是类似于dp的问题，

而最小生成树和他的区别就是他的边的价值差足够大导致边之间距离和的约束已经不起作用。

他只考虑最小。所以说很多情况不能乱用最小生成树，类似于很多dp没有贪心性质。

例题：

这个问题看似是最短路问题，但是有两个问题： 一，会被砍 $log$ 。 二，直接是 $n^2$ 的。 我们发现边权差距非常大，比某条边小的所有边加起来都不如这条边，所以建出最小生成树，而任意两点间的最短路就是生成树上的任意两点间路径，可以简单用siz维护。 ------------ #### 基于删点一类问题tarjan和最小生成树的对比： 对于此类问题，我们通常是把未被删点的图处理掉再考虑贡献。 例题： 给定一个有向图，问删除每个点之后至少要建多少个点才能使得每个未被删的点都有路径到达选定点集。 这个问题跟矿场搭建类似，但是是在有向图上。通过这个问题我们可以知道割点不一定只存在于无向图。 我们考虑tarjan求出强联通分量，用双连通分量类似的方法求出有向图割点，将原图分成若干连通块。 如果一个连通块内没有割点，那么需要建两个点。 如果一个连通块有两个割点，不用管。 如果一个连通块有一个割点，在这个割点处建，而且再找一个位置建。 例题： 给定一张无向图，求删掉每个点之后的最小生成树。 我们建出最小生成树，然后dfs。对于一个点被删掉，能重新被启用的边要么是把两个子树连起来的边，这个均摊下来是 $m$ 的，要么是子树向上的一条边，可以用树上差分或者树上并查集简单维护，然后再做kruscal即可。 ------------ #### 并查集和最小生成树的对比： 例题1： 你要在以原点为圆心半径为 $x$ 的圆内活动，平面上还有一些半径为 $y$ 的障碍，现在从原点向东南西北四个方向发出射线，射线会以一定速度顺时针旋转无数圈，问你是否能找到一个初始位置和移动方案，使得不碰到射线，不碰到障碍物同时还要在半径为 $x$ 的圆内。 这个问题我们发现如果两个障碍距离小于 $2x$ 或者障碍到起点距离小于 $x$ ，那么就不能跨过这两个障碍之间的这段圆环了,可以看做连了一条边，问题转化为是否有从起点到终点 $(也就是边界)$ 的一条链，这个东西就可以用并查集来维护。 例题2：SDOI2012拯救小云公主 Boss的洞穴可以看成一个矩形，英雄在左下角 $(1,1)$ ，公主在右上角 $(row，line)$ 。英雄为了避开boss，当然是离boss距离越远越好了，所以英雄决定找一条路径使到距离boss的最短距离最远。 把答案视为Boss的攻击半径，题目就变成了给你一个矩形中有一些圆，问能否找到一条从左下角到右上角的路径不经过任何一个圆。 如果我们把圆看成奶酪上的一些洞，则当左边界或上边界通过这些洞和右边界或下边界联通时问题无解。 以上为这道题第一篇题解的思路。 我们发现bfs完全没有必要，我们直接用一个并查集就能维护。 但是二分+并查集这个东西同样很鸡肋。 考虑每次重新二分非常冗余，我们可以用排序来均摊掉这个二分。 什么？你说排序还是一个 $log$ ？还想用基数排序？ 我们发现排序+并查集就是最小生成树！ 直接prim，复杂度降至 $n^2$ 。由此我们可以得出像这种好多圆不停扩大的问题我们都可以想想能不能规约到连通性问题。 这个题还有一个给我们的启发是kruscal也可以反着转化回排序+并查集。 比如说NOIP 2013货车运输： A 国有 $n$ 座城市，编号从 $1$ 到 $n$ 城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。 现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 这个题是道最小生成树+lca的经典题，但是我们可以砍掉这个 $log$ 。 把边离线下来桶排序，每遇到一条边用并查集合并，可以降到近似线性。 ------------ #### 一类和tarjan解决的问题类似的算法 dfs动态维护： 这个在某些情况有奇效，但是由于tarjan是强联通算法，而dfs不是，所以有些tarjan能处理的情况dfs动态维护处理不了。 给定 $m$ 条有向边，你需要分最少的组使得每一组的边编号连续且每一组没有 $1-n$ 的路径。 考虑动态维护加边， 如果两个点都被访问过了，不管。 如果一个点没被访问过一个点被访问过了，进入没被访问过的点dfs。 如果两个点都没被访问过，把这条边挂在边表上。 于是就能巧妙地做到线性了。 ------------ #### 最小生成树引出的两个算法 lct&线段树分治维护连通性：这是这两个算法的基本应用，多数情况下离线线段树分治和lct是等价的。需要注意的是这两个数据结构维护最小生成树的套路，下文讲最小生成树连通性的时候不妨体会一下lct维护连通性。 放三道例题吧： 魔法森林：排序+lct。 最小mex生成树：线段树分治。 最小极差生成树：lct。 ------------ #### 本文规约实际应用的例子 类似“二维偏序”的连通性问题： 有的时候一个题非常丧心病狂，他会二合一，每条边有两组属性，第一条边跟最短路有关，第二条边跟连通性有关，还是一定范围内的连通性，这时就不能简单的直接最小生成树了。 例题：NOI 2016 归程 这个题首先跑最短路，问题就转化成上述问题，众所周知有个维护二维偏序的东西叫作可持久化线段树，然而可持久化线段树不能维护最小生成树。 那怎么办呢？ 根据上面的连通性理论,生成树本质是sort+并查集，我们不妨将sort去掉， 使用可持久化线段树维护并查集。 或者，我们可以使用另外一个叫作kruscal重构树的黑科技，这个东西可以解决 在一定边权限制范围内的问题，考虑倍增从给定结点跳到一个最浅符合范围的结点，这个结点的子树就是所有能到达的点。 这样，我们成功解释了为什么这道题可以用可持久化并查集或者kruscal重构树这两个毫不相关的东西解决问题。 例题: 给定 $v$ ,查询单点 $v$ 的权值。 给定 $x,y,v$ , 对于在子树 $v$ 内的所有节点 $u$ ,如果 $(u,v)$ 路径上所有边权都 $\ge y$ , 就将点$u$的权值增加 $x$ 。 这个问题我们发现有 $\ge y$ 的限制也有子树的限制，我们建出kruscal重构树问题就变成两个子树的交，这个东西就是带修二维偏序，可以选一个偏序问题的算法解决。 例题： 给定一个 $n$ 个点、 $m$ 条边的带权无向图，其中有 $s$ 个点是加油站。 每辆车都有一个油量上限 $b$ ，即每次行走距离不能超过 $b$ ，但在加油站可以补满。 $q$ 次询问，每次给出 $x,y,b$ ，表示出发点是 $x$ ，终点是 $y$ ，油量上限为 $b$ ，且保证 $x$ 点和 $y$ 点都是加油站，请回答能否从 $x$ 走到 $y$ 。 为了回答每个询问，我们需要加油站之间的最小生成树。 求最小生成树的方式是：让所有的加油站 $dis$ 为0，做多源最短路，同时记录距离每个点最近的加油站。然后枚举边，可以得到两个加油站之间的可能最短距离。做Kruskal或Prim即可。 最小生成树之后，用倍增维护路径上的最大权值即可。 ------------ #### 最小生成树和tarjan本质联系 支配树：来自于tarjan，所以也能解决支配点一类的连通性问题。 最小树形图，又可以算有向图最小生成树，也是用tarjan生成的。 这就可以解释tarjan和最小生成树的内在联系。 ------------ #### 类似“插头dp”的连通性问题： 插头dp是针对数据范围较小，跟所有算法基本上都没太大关系的连通性问题。这里不提，我们要提的是类似插头dp的连通性问题： 给定一个网格图，有些位置已经被涂色。要求构造两个相同大小的网格图，并且在上面涂色，需要保证颜色四联通。满足这两个网格的涂色部分的重合位置恰好是给定的网格图的涂色位置。 这个问题看起来非常棘手，考虑这样构造类似插头的东西， ``` ####. ....# #.... .#### ####. ....# #.... .#### ####. ....# ``` 然后对于每个已经被涂色的位置我们在两张图上染上颜色，我们惊奇的发现正好满足所有条件！ # 总结： 众所周知偏序问题有一个比较完备的理论，在这一段时间里，我发现连通性也是有相关联系的，很多东西都是能互换或者解释的通的，希望对大家有所启发。