题解：P3387 【模板】缩点

csxx601cjy · 2025-05-04 22:21:16 · 题解

题解：P3387 【模板】缩点

upd：

• 2025/5/31：修复挂掉的图，完善文章细节。
• 2025/10/5：换了个图床（用 github 存图片访问实在太慢了！）

可能更好的阅读体验：https://0xcjy.github.io/oi/graph/suodian。

算法介绍

概念

缩点（Contraction of Strongly Connected Components）是图论中对有向图进行简化的重要操作，其核心是将图中的强连通分量（SCC）合并为单个节点。

强连通分量定义：在有向图中，若任意两个节点 u 和 v 之间存在双向路径，则这些节点构成强连通分量。该分量是满足此条件的极大节点集合。

Tarjan 算法由计算机科学家 Robert Tarjan 于 1972 年提出，是一种基于深度优先搜索（DFS）的图论算法，主要用于求解有向图的强连通分量、无向图的割点、无向图的桥。

拓扑排序是对有向无环图（DAG）顶点的一种线性序列化方法，使得对于任何的顶点 u 到 v 的有向边, 都可以有 u 在 v 的前面。

流程

Tarjan（参考 OI-wiki）

Tarjan 算法基于对图进行深度优先搜索。我们视每个连通分量为搜索树中的一棵子树，在搜索过程中，维护一个栈，每次把搜索树中尚未处理的节点加入栈中。

在 Tarjan 算法中为每个结点 u 维护了以下几个变量：

2. 设以 $u$ 为根的子树为 $Subtree_u$。 定义为以下结点的最小值： - $Subtree_u$ 中的结点 - 从通过一条不在搜索树上的边能到达 $Subtree_u$ 的结点

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfn 与 low 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 u 和与其相邻的结点 v（v 不是 u 的父节点）考虑三种情况：

这么说不是很直观，用一个例子演示：

12 21
1 2 3 4 5 6 7 8 9 10 11 12
1 2
2 3
3 4
4 1
5 6
6 5
7 8
8 9
9 7
4 5
6 7
9 10
10 11
11 12
12 11
12 9
3 7
1 5
5 7
7 10
10 12

下面这张动图演示了 Tarjan 算法的流程，其中黑色数字是结点编号（为了方便，dfn 和点权也是同样的数字），红色数字是 low，被彩色笔圈起来表示出栈了，不同颜色代表不同强连通分量。这个例子中，一共有三个强连通分量（绘制不易，点个赞不过分吧）。

对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 u 使得 dfn_u=low_u。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 dfn 和 low 值最小，不会被该连通分量中的其他结点所影响。

因此，在回溯的过程中，判定 dfn_u=low_u 是否成立，如果成立，则栈中 u 及其上方的结点构成一个强连通分量。

缩点

看标题就知道，这是本题的关键。为什么要缩点呢？因为这张图不是 DAG（有向无环图），无法通过 DP 的方式求出答案。仔细思考一下，既然一个强连通分量里所有的点都可以互相到达，我们就可以不用管它的内部结构，直接把它当作成一个点，不就行了吗。这就是缩点。别忘了融合后的点权值是所在强连通分量里所有点的权值之和。缩点之后，这张图变成了一个 DAG，就可以求了。

至于怎么缩点，可以建一个新图，把融合后的点和连接两个不同强连通分量的边加入新图就可以了。

缩好点后的图长这样，是一个 DAG：

用肉眼就能很容易看出来，这幅图答案为 78。

拓扑排序

有人可能不知道为什么拓扑排序可以求 DAG 的最大权值路径的权值。它其实是和 DP 有关的，用类似 Bellman-Ford 的松弛，写出状态转移方程：

而 DP 执行的顺序，就是拓扑排序的顺序。

答案就是 \max_{i=1}^n dp_i。

拓扑排序的流程想必大家都会，不会可以看 OI-wiki，我就不过多介绍了。

正确性证明

强连通分量（SCC）缩点的正确性

• 性质：一个强连通分量内的所有节点可以互相到达。因此，若路径经过该分量中的任意节点，总能调整路径使其访问分量内所有节点（从而权值总和固定为该分量的权值之和）。
• 权值合并：将每个 SCC 的权值设为内部所有节点权值之和。无论路径如何经过该分量，权值贡献最大化为该总和，重复访问不会增加权值。
• 路径映射：原图中的路径对应缩点后 DAG 中的路径。例如，原路径 A→B→C（B、C 属于同一 SCC）会被映射为 A→SCC_B，而 SCC_B 的权值包含 B、C 的权值总和。

DAG 构造的正确性

• 无环性：SCC 之间不存在循环依赖，否则这些 SCC 会被合并为一个更大的 SCC。因此，缩点后的图是 DAG。
• 拓扑序的可行性：DAG 的拓扑排序能保证处理节点时，所有前驱节点的状态已计算完成，为动态规划提供基础。

tarjan

有关 tarjan 算法的证明，可以参考一篇博客。

时间复杂度证明

Tarjan

Tarjan 算法通过 DFS 遍历所有节点和边，每个节点入栈、出栈各一次，每条边被访问一次，因此为 O(n+m)。

缩点构建 DAG

1. 合并 SCC 权值：遍历每个节点，累加其所属 SCC 的权值，复杂度 O(n)。
2. 建立 DAG 边：遍历原图所有边，若两端点属于不同 SCC，则在对应 SCC 间添加边，复杂度 O(m)。

拓扑排序和 DP

时间复杂度 O(k+e)（k 为 SCC 数量，e 为 DAG 边数）

基于入度队列实现，每个 SCC 节点和边处理一次，复杂度 O(k+e)。

总复杂度