1. 这道模板题凭什么值得单独写一篇洛谷P3387的题目叫【模板】缩点我当年刷到它的时候第一反应是“这不就是数环吗”结果真正动手写才发现缩点根本不是把环找出来这么简单它背后牵扯的是一整套关于有向图强连通分量SCC的理论和一套极其优雅的Tarjan算法。如果你刚学完强连通分量想找一道题把理论和实践串起来P3387就是那个最合适的练手点。先看题目在说什么。给一张有向图每个点上带一个权值要求从任意点出发可以沿着有向边走把经过的点的权值累加一个点可以重复经过但权值只算一次问能得到的最大点权和是多少。这个约束条件很关键——“一个点可以重复经过但权值只算一次”。它意味着什么意味着如果图里存在一个环你只要进入环内就能把整个环的所有点权全部拿一遍然后从环上任意一个点离开继续往下走。环在这里就是一个“整体打包”的单位。既然是一个整体那为什么不把它压缩成一个点呢这就是缩点最朴素也最核心的动机。所以这道题有两个层面的价值。表层价值是让你学会一道经典图论题的写法深层价值是让你理解一个重要的思维范式在有向图中环是DP动态规划的破坏者而缩点是修复这个破坏的最直接手段。把有向图缩成有向无环图DAG之后所有的环都消失了于是你就可以放心大胆地在上面做拓扑序DP或记忆化搜索不会陷入循环依赖的死结。这篇文章我打算按我实际做题时的思考顺序来写先搞懂Tarjan在算什么再看缩点是怎么建的然后研究缩点后的新图怎么跑DP拿答案最后把我踩过的坑和调试思路全部倒出来。每一项都是我当时翻了很多题解才弄明白的现在整理成一份你可以直接照着一路AC的完整攻略。2. 强连通分量与Tarjan算法理解这五个核心细节就够用了2.1 强连通分量的定义以及它和“环”的区别强连通分量的定义很简洁在有向图中如果两个顶点u、v互相可达存在从u到v的路径也存在从v到u的路径那么u、v属于同一个强连通分量。一个强连通分量是极大的顶点集合集合内任意两点互相可达。注意强连通分量不一定是环。比如两个点之间有一条双向边这两个点构成一个强连通分量但它不构成一个“环”。再比如一个单独的顶点它自己到自己是可达的路径长度为0所以单点也是一个强连通分量。这一点经常被初学者忽略导致连Tarjan初始化时容易忘记每个点是独立的SCC。题目里还可能出现自环也就是点u指向u自己的边。自环不会影响Tarjan的正确性但会在缩点后的建图阶段带来一点点麻烦后面我会专门讲。总之强连通分量的本质是“互相可达的等价类”环是最典型的形态但不是唯一形态。2.2 Tarjan的两个灵魂数组dfn和lowTarjan算法基于DFS遍历核心是维护两个数组dfn[u]顶点u被DFS访问到的顺序编号也叫时间戳。low[u]顶点u能够回溯到的最早时间戳。更准确地说是从u出发通过DFS树中的子树边以及最多一条非树边返祖边能够到达的顶点其dfn的最小值。我当年学Tarjan的时候最困惑的就是low的含义。用大白话讲low[u]表示从u这个点出发在DFS的搜索过程中能绕回的最靠上的那个祖先是谁。如果u的某个后代有一条返祖边直接指到了u的祖先那u的low就会被拉高其实是拉小数值变小。如果u及其后代无论怎么走都只能到达自己人那这个连通分量就到此为止该出栈结算了。看这个细节就明白Tarjan本质上是在DFS的过程中追踪“返祖边”的能力。有向图的复杂度就在这边的方向决定了返祖边能把low拉回到什么位置。2.3 栈的作用维护“正在形成”的强连通分量Tarjan需要一个辅助栈这个栈的作用不是记录整棵DFS树的路径而是只记录当前还未被确定属于任何SCC的顶点。也就是说栈里的元素是“处理了一半、还没定性”的候选者。当一个节点的dfn访问完毕它的所有子树也递归处理完毕此时检查if (low[u] dfn[u]) { // u是某个强连通分量的根 // 从栈中弹出顶点直到弹出u为止 }为什么low[u] dfn[u]就能断定u是一个SCC的根因为如果u的low比自己小说明u能绕回到某个真正的祖先那u就不可能是这个分量的最高点它必然属于祖先所在的SCC而如果low等于dfn说明它的后代无论怎么绕都绕不出u这个范围所有能到达的点都在以u为根的DFS子树内这些点互相可达正好构成一个极大的强连通分量。这里有三个注意点栈顶弹出的顺序恰好是搜索时入栈的逆序但这不重要重要的是栈中从栈顶到u之间的所有点恰好构成一个完整的SCC。low[u] dfn[u]的判断本质上是“这个分量的根是谁”不是“这个点是不是孤立点”。一个独立的点也是SCC它的dfn和low相等会自己出栈。栈的元素是在DFS的深入过程中逐渐累积的所以递归返回时需要从栈中弹出但在递归未返回时栈顶始终是最新进入搜索的顶点。2.4 Tarjan算法的手动推演从样例到代码为了把上面这些概念串起来我手动推演一个极简的图3个点边为1→2、2→3、3→1以及3→4、4→5权值这里先不管。求SCC。从点1开始DFS访问1dfn[1]1low[1]1入栈。从1走到2dfn[2]2low[2]2入栈。从2走到3dfn[3]3low[3]3入栈。从3走到1发现1已经在栈中且正在被处理这是关键条件见下一节用dfn[1]1去更新low[3]low[3]1。3的邻接边遍历完毕递归返回到2用low[3]更新low[2]low[2]1。同理返回到1用low[2]更新low[1]low[1]1。1的邻接边还有一条到4吗没有这个例子里1到4没有边。所以1处理完毕low[1]dfn[1]从栈中弹出3、2、1这三个点构成一个SCC1,2,3。注意出栈顺序是3、2、1恰好是入栈逆序。接下来从4开始DFS访问4dfn[4]4low[4]4入栈。走到5dfn[5]5low[5]5入栈。5没有出边low[5]dfn[5]弹出5单点SCC5。回到44没有其他出边low[4]dfn[4]弹出4单点SCC4。最终得到3个SCC分别是1,2,3、4、5。这个推演过程看起来很顺但实际代码里有几个容易出错的细节下一节继续说。2.5 判断条件为什么是“在栈中”而不是“已访问”Tarjan在更新low时有一条边判断这是新手最容易写错的地方if (邻接顶点v尚未访问) { dfs(v); low[u] min(low[u], low[v]); } else if (v还在栈中) { low[u] min(low[u], dfn[v]); }这里的关键是第二个分支用dfn[v]而不是low[v]更新low。为什么因为v如果是通过返祖边到达的祖先v此时一定在栈中但v所在的SCC可能还未完全闭合。如果在这个时刻用low[v]更新可能会把某个尚在处理中的分量的low传播过来导致真正的根判断错误。而用dfn[v]更新表示的是“我能回到时间戳为dfn[v]的那个祖先”这是稳的不依赖v的子树处理状态。另外为什么已访问但已出栈的节点不能用来更新low因为一个节点一旦出栈代表它的SCC已经确定它不可能再与当前正在搜索的节点互相可达否则它们应该在同一个SCC中一起出栈。所以已出栈的节点对当前节点的low没有任何贡献。这个判断逻辑是整个Tarjan算法里最容易写挂的地方我见过不少AC代码在判断条件上写成了if (!vis[v])然后在else分支里不管是否在栈中都更新low这种写法在随机数据上可能侥幸过但在某些构造数据下会直接WA。老老实实按“在栈中”判断才能保证正确性。3. 从SCC到缩点DAG建图阶段的所有细节3.1 缩点的本质把每个SCC看成新图中的一个节点我们求完全部SCC之后要做的事情是“把每个SCC压缩成一个点”。压缩不是简单地把点合并而是要做两件事合并权值SCC内所有点的权值之和就是缩点后新节点的权值。因为在原图里只要你进入这个SCC就能把所有点的权值都走一遍。保留边关系如果原图中存在边u→v且u和v不在同一个SCC里那么在新图中从u所属的SCC连一条边到v所属的SCC。建图时最常用的方法是开辟一个染色数组color[u]表示原图点u属于哪个SCC编号。Tarjan每次找到一个完整的SCC时给这个SCC分配一个编号并把弹出的所有点的color都设置为这个编号。vectorint sccId(n 1, 0); int sccCnt 0; // Tarjan内部判断到low[u] dfn[u]时 sccCnt; while (true) { int v stk.back(); stk.pop_back(); sccId[v] sccCnt; sccWeight[sccCnt] w[v]; if (v u) break; }注意弹出时要把权值累加到一起这个sccWeight数组是后面DP的依据。3.2 遍历原图边建新图的所有注意事项染色完成之后重新遍历原图的每一条边。对每条边u→v如果sccId[u] sccId[v]说明这是SCC内部的边忽略。否则在新图中添加一条边addEdge(sccId[u], sccId[v])。这里有一个细节很多人在这个阶段会纠结“要不要去重”。其实不需要去重。两个新节点之间即使有多条边在DP时它们的意义等价于一条边不会影响结果。重边只会让邻接表多几个元素对答案没有负面影响除非你用某些特殊的算法对边的数量敏感否则直接保留即可。不过有一个例外要注意如果原图中存在自环u→u那在缩点后的新图里这个自环会被合并到SCC内部因为u和u当然属于同一个SCC所以它会在sccId[u] sccId[v]的分支里被忽略不会产生新图中的自环。3.3 新图一定是DAG——为什么这很关键缩点之后的新图必定是有向无环图。这个结论很重要因为它是后续DP能成立的基础。证明思路很直接如果新图中还存在一个环那么环上的所有新节点对应原图中的若干SCC首尾相连形成更大的互相可达关系这跟“极大强连通分量”的定义矛盾。所以不可能存在环。既然没有环就可以用拓扑序DP或记忆化搜索来求最优值。这意味着我们不用再担心环造成的无限循环或相互依赖。从任意一个SCC出发沿着边走下去一定会终止路的长度是有限的。3.4 新图的入度出度后续DP排序的依据建图时顺手统计每个新节点的入度因为之后拓扑排序会用到。这个统计不难for (int u 1; u n; u) { for (int v : originalGraph[u]) { if (sccId[u] ! sccId[v]) { newGraph[sccId[u]].push_back(sccId[v]); indeg[sccId[v]]; } } }有了入度数组跑拓扑排序时以入度为0的节点作为起点。但这里有个容易想错的地方DP的起点到底是什么题目允许从任意点出发所以入度为0的节点当然可以作为起点但并非只能从入度为0的节点出发。更准确的表述是当我们做拓扑序DP时本质上是在计算“以每个节点为结束点的最大收益”所以理论上所有节点都应该参与DP不能只从入度为0的节点开始。大部分题解的写法是遍历所有节点对每个节点做一次记忆化搜索或者按拓扑序把所有节点都处理一遍。这样才能保证最终答案覆盖从任意点出发的所有情况。3.5 一个小细节新图的根与拓扑序的等价物Tarjan在弹栈时SCC的编号是按DFS完成顺序递增的。这个顺序有一个有趣的特性SCC编号的逆序恰好是一种合法的拓扑序。这一点可以从Tarjan的递归结构推导出来一个SCC能到达的另一个SCC必然在DFS树中后访问或更晚完成。所以很多代码不写拓扑排序而是直接从sccCnt递减遍历来更新DP效果是一样的。我当时第一次看到这个结论觉得像魔法自己推演了一遍才确信。不过如果你不想依赖这个性质老老实实写一个拓扑排序也完全没问题。两种做法都会在后面的DP章节详细介绍。4. 缩点后的DP在DAG上求总权值最大的路径4.1 DP状态定义f[i]表示以节点i为终点的最大权值和缩点后的新图是一个DAG我们要在新图上找一条路径使得路径上所有点的权值之和最大。因为点权都为正题目保证点权为正数所以路径越长、覆盖的权值越多越好但这不意味着每条边都一定要走——之后的点有没有出边都不影响当前路径的收益。标准的DP状态设计是f[i]表示从某个起点出发到达节点i时能够得到的最大点权和包含节点i本身的权值。转移方程f[to] max(f[to], f[u] sccWeight[to])这个方程要从u推to就必须保证当u被用于转移时它的f值已经被彻底算好了。这正是拓扑序的必要性只有在前驱节点全部处理完之后当前节点的f值才是最终的。如果直接按节点编号顺序处理可能前面用到u时u还没被更新到最优值那后面的转移就会出错。拓扑排序或记忆化搜索都是为了解决这个顺序问题。4.2 方案一拓扑序DP的完整流程先对新图做拓扑排序得到拓扑序列数组topo。之后按拓扑序遍历每取出一个节点u就尝试用它去更新所有后继节点for (int i 1; i sccCnt; i) { int u topo[i]; for (int v : newGraph[u]) { f[v] max(f[v], f[u] sccWeight[v]); } }初始时f[i] sccWeight[i]因为可以从节点i自己出发不经过任何前驱。答案就是所有f[i]的最大值。这个写法很直观但有一个必须注意的细节拓扑排序本身的实现。新图节点的编号是1到sccCnt入度数组indeg是在建新图时统计的。用队列维护入度为0的节点每弹出u就把u的所有后继v的入度减1。这个流程非常简单不再赘述。4.3 方案二记忆化搜索的简捷之处记忆化搜索是另一种常见写法我个人觉得对于P3387这种规模的题目n和m最多1e4记忆化搜索写起来更省心因为它不需要建拓扑序也不需要开队列逻辑上更贴近“从每个起点出发搜索”的直觉int dfs(int u) { if (dp[u] ! -1) return dp[u]; dp[u] sccWeight[u]; for (int v : newGraph[u]) { dp[u] max(dp[u], sccWeight[u] dfs(v)); } return dp[u]; }然后用循环对所有节点调用dfs(i)取最大值。这个写法里dp[u]表示从u出发能获得的最大路径权值和包含u。“从任意点出发”自然就转化为“从每个可能的u出发”取最大值。因为DAG无环递归不会无限下去。记忆化搜索的缺点是递归深度可能受系统栈限制。P3387的n最大1e4加上建图数据递归深度可能接近n在部分OJ上可能会爆栈。如果遇到这种情况要么改成拓扑序DP要么用#pragma comment(linker, /STACK:1024000000)Windows或其他手段加大栈空间。4.4 两种方案选哪个我的实际取舍我个人的建议是如果是为了刷题比赛记忆化搜索更不容易写错如果是为了理解算法的本质拓扑序DP更有助于体会“DAG上DP为什么依赖拓扑序”。在洛谷P3387的数据范围下n,m ≤ 10^4递归深度一万层内存栈在很多评测机上都能扛住所以两个方案都能过。但如果你是在别的OJ上做题数据范围更大尽量用拓扑序DP图省事用记忆化搜索也没大问题只要不爆栈。我曾经在另一道题n到10^5上因为盲目用递归记忆化搜索狠狠地TLERE了一回后来改成拓扑序DP才过。那道题也让我养成一个习惯图论题涉及DP时先看一眼数据规模再决定用哪种写法。数据超过2万还带长链的优先拓扑序DP。4.5 为什么答案不是“从入度为0的点开始DP的结果”这题的题目描述是“可以任选一个点开始”很多人理解为只能从入度为0的点开始。这是不对的。假设一个点入度不为0但所有前驱节点都在一个权值很低的SCC里从它自己出发反而能绕过那些低权值的前驱获得更高的收益。举例说明新图有三个节点A、B、CA→CB→C。A的权值为1B的权值为100C的权值为1。A、B的入度都为0C的入度为2。如果只从入度为0的点出发DP初始值分别是f[A]1、f[B]100然后更新Cf[C]max(11, 1001)101。这没问题。但如果有一条边D→B且D权值为5B权值为100C权值为1。D的入度为0B的入度为1。若只从入度为0的点出发DPD→B更新后f[B]105。看起来没问题。关键在于如果B的某个入度前驱权值很大而从前驱走到B路径收益不如直接从B出发呢由于点权为正经过前驱只会让累计值变大所以入度处理一定不会让B的最佳值变小。也就是说从任意前驱走到B得到的值一定大于等于sccWeight[B]本身。因此理论上从入度为0的点出发DP并把所有入度不为0的节点也纳入转移因为它们在拓扑序中迟早会被处理到是可以覆盖所有最优解的。严谨一点说答案确实只可能从入度为0的点“开始展开”的路径中获得吗不一定因为如果某个节点i的入度全部来自权值和极小的分支但分支太小直接忽略分支从入度为0的起点出发的路径也可能不是最优。但在拓扑序DP的实现中我们并不只初始化入度为0的点而是初始化了所有节点f[i]sccWeight[i]。这样即使存在一条路径从某个节点中间开始只要中间节点本身被初始化了它就可能成为某条路径的“伪起点”。所以正确说法是所有节点都要初始化所有节点都要被处理。不要只从入度为0的节点开始推进。宁可在拓扑排序时把所有节点放入初始队列也就是把所有入度为0的节点放入队列但DP初始化所有节点然后在更新时所有节点都会被自然处理到答案取所有f的最大值。4.6 验证一个边界情况单点SCC与孤立SCC如果原图本身就是一片离散的点没有任何边那每个点单独成SCC缩点后的新图也没有边。此时f[i]初始化为sccWeight[i]就是原权值答案就是最大点权。这符合常识因为最优策略就是选一个权值最大的点直接结束。如果原图是一个大强连通分量缩点之后只有一个节点。此时新图没有边答案是整个SCC的权值之和。这也符合直觉——在这个强连通分量里你可以把所有权值都拿一遍。这些边界情况在写代码时都要想到否则容易在初始化和答案取值时出问题。5. 完整代码模板与逐段注释下面是整个P3387的C代码模板我已经把关键注释写在代码行内方便直接对照理解。这个模板是我个人惯用的写法跑过洛谷的数据稳定AC。#include bits/stdc.h using namespace std; const int MAXN 10005; int n, m; int w[MAXN]; // 原图点权 vectorint g[MAXN]; // 原图邻接表 int w2[MAXN]; // 缩点后点权 vectorint g2[MAXN]; // 缩点后邻接表 int indeg[MAXN]; // 缩点后入度 int dfn[MAXN], low[MAXN], timerCnt; int sccId[MAXN], sccCnt; int stk[MAXN], top; bool inStk[MAXN]; int f[MAXN]; // 拓扑序DP用 vectorint topo; void tarjan(int u) { dfn[u] low[u] timerCnt; stk[top] u; inStk[u] true; for (int v : g[u]) { if (!dfn[v]) { // 未访问过 tarjan(v); low[u] min(low[u], low[v]); } else if (inStk[v]) { // 已访问且在栈中 low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { sccCnt; while (true) { int x stk[top--]; inStk[x] false; sccId[x] sccCnt; w2[sccCnt] w[x]; if (x u) break; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) cin w[i]; for (int i 1; i m; i) { int u, v; cin u v; g[u].push_back(v); } // 第一遍Tarjan找SCC for (int i 1; i n; i) { if (!dfn[i]) tarjan(i); } // 缩点建图 for (int u 1; u n; u) { for (int v : g[u]) { if (sccId[u] ! sccId[v]) { g2[sccId[u]].push_back(sccId[v]); indeg[sccId[v]]; } } } // 拓扑排序 queueint q; for (int i 1; i sccCnt; i) { f[i] w2[i]; if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for (int v : g2[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } // DAG上做DP int ans 0; for (int u : topo) { ans max(ans, f[u]); for (int v : g2[u]) { f[v] max(f[v], f[u] w2[v]); } } cout ans \n; return 0; }这段代码有几个点值得再强调Tarjan里是用数组手写栈不是用STL的stack。手写栈的好处是访问栈顶元素方便弹栈逻辑也更直观性能略好。当然用std::stack也可以看个人习惯。建新图时没有去重前面说了没必要。拓扑排序用queue实现所有入度为0的节点入队。DP时按拓扑序遍历整个拓扑序列而不是只处理guaranteed起点。5.1 换成记忆化搜索的版本如果你想用记忆化搜索只需要在缩点建图之后换成下面这段逻辑int dp[MAXN]; int dfs(int u) { if (dp[u] ! -1) return dp[u]; dp[u] w2[u]; for (int v : g2[u]) { dp[u] max(dp[u], w2[u] dfs(v)); } return dp[u]; } // 在主函数中 memset(dp, -1, sizeof(dp)); int ans 0; for (int i 1; i sccCnt; i) { ans max(ans, dfs(i)); } cout ans \n;注意这个写法里dp[u] max(dp[u], w2[u] dfs(v))而不是dp[u] max(dp[u], dfs(v))。因为dfs(v)表示从v出发的最大收益不包含u的权值所以必须把u自己的权值加上。很多人第一次写容易漏掉这个w2[u]导致答案恰好少了起点的权值。5.2 两种版本的性能对比从常数上看拓扑序DP更占优因为它是纯粹的数组迭代没有递归调用开销。记忆化搜索在数据规模小的时候看不出差别但每次递归都有函数调用开销遇上1e4个节点的长链时间也完全可以接受1e4次递归每次常数操作绰绰有余。真正的问题在于递归爆栈风险而不是时间。如果你在洛谷上提交m和n最大1e4递归深度最多也是1e4通常不会爆栈。但如果你换个OJ数据范围到了1e5甚至更大那还是用拓扑序DP更稳。6. 从TLE到AC调试过程中的坑与排查思路6.1 我踩过的第一个坑Tarjan循环里误把原图的点编号当新图编号这是我第一次做P3387时犯的错误也是不少初学者的通病在缩点重建图之后下意识地拿原图点编号去更新新图的f数组。比如写完缩点后做DP时写了f[v] max(f[v], f[u] w[v])这里的u、v还在用原图节点编号而f和w2针对的是新图节点编号。这种错误跑样例可能刚好能过因为样例里的缩点关系简单加上输出恰好碰巧一致但换一组数据就直接WA。排查方法在所有涉及新图的数组操作处都确认下标是从sccId转换过来的。写代码的时候可以在建图阶段加一句assert(sccId[u] 1 sccId[u] sccCnt)帮助定位。6.2 我踩过的第二个坑low更新条件漏掉inStack判断我前面强调过else if (inStk[v]) { low[u] min(low[u], dfn[v]); }如果你写成了else { low[u] min(low[u], dfn[v]); }会把已经出栈的点也算进去。这个问题在大多数随机图上可能测不出来因为“已经出栈且存在一条边回到当前点”的情况不多见。但在严格构造的图上比如两个或多个SCC之间存在交叉引用很容易出现。我当时是自己构造了好几组图来验证的后来才彻底搞明白为什么必须是inStk判断。这里建议你实际画一画下面这个图点1、2构成一个SCC点3、4构成另一个SCC边包括1→2、2→1、2→3、3→4、4→3再加上4→1这种环外的边。如果缺少inStk判断在访问点4时发现1已经在栈外但错误地用dfn[1]更新low[4]low[4]会变成1导致4和1被错误划分进同一个SCC。这会把两个SCC错误合并进而让缩点后的图变得完全不是DAGDP结果自然也不对。6.3 我踩过的第三个坑答案取max时漏掉了单点出发的情况如果我只把f初始化为0然后从每个入度为0的节点开始更新最终答案可能漏掉“从中间某个节点出发”这种情况。虽然前面说过由于点权为正从前驱走到当前节点的收益一定不小于当前节点自身但万一中间节点没有可用的前驱能到达它呢也就是它入度为0这没问题万一它有前驱但前驱的收益因为某种原因没传过来呢拓扑排序会保证前驱先被处理前驱的f一定已经包含它的最大收益所以f[当前]一定也被更新过。但问题出在初始化上如果一开始f[i]0某个节点从自己出发的收益是0w2[i]w2[i]这没问题但如果某个节点的前驱很多按拓扑序更新下来不会漏。真正会漏的是“从自己出发”这种路径在初始化时被忽略了。稳妥的做法是初始化时f[i]w2[i]就像我的模板那样。这样每一步都包含了从自己出发的收益后面的更新只会大于等于这个值。6.4 一个隐蔽的错误拓扑排序队列初始化未包含所有入度为0的节点有时候建图时统计indeg是在原图边上循环时累加的缩点的过程中可能漏掉若干条边导致入度偏小。虽然入度偏小会让更多节点进入拓扑序队列看起来结果不会错但实际上如果漏加了某条边拓扑排序会产生一个错误的顺序某些节点的前驱没有先被处理到DP就会出问题。解决这个问题的最好方式是建新图时专门用一个独立的循环统计入度不要和Tarjan代码混在一起。我在模板里就是这么做的——先跑完Tarjan再单独遍历原图所有边来建新图和统计入度。这样树上的逻辑清晰不容易漏。另外如果新图里有重边入度会重复累加。拓扑排序时每个重边都会减一次入度因此不会死锁结果依然正确。这算是一个很幸运的性质但如果用某些“只保留一条边”的建图方式反而要小心入度统计必须和建边保持一致。6.5 性能排查为什么我的程序TLE了P3387的数据量是1e4点、1e4边理论上任何复杂度正常的算法都能过。如果你的程序跑得慢通常只有两种可能Tarjan的递归深度太深且没用编译优化不过1e4深度不至于超时只可能爆栈。你在某些循环里用了O(n²)的操作比如建新图时用set去重或者每个节点都遍历一遍sccCnt导致总复杂度变成1e8级别。1e8在1秒内对C来说很吃紧稍有不慎就TLE。我的建议是不要在新图上使用set/unordered_set去重没必要。邻接表直接push_back就行。查找操作或去重操作消耗的时间远大于重边带来的影响。6.6 万能调试手段构造小图手工验证如果WA了别急着看数据先自己构造几个小图把答案手算出来再跑程序对比。这个习惯是我刷算法题最受益的习惯之一。针对P3387建议至少构造下面几种小图一个单点、没有边看看答案是不是这个点的权值。一个长度为3的环看看答案是不是三个点权之和。一个入度为0的A连到环上环上再连到出度为0的B看看能否正确累加全部权值。两个不相连的强连通分量分别带点权看看答案是否是权值更大的那个。一条长链上每个点都是独立SCC验证DP是否按拓扑序累加。这些构造都能帮你快速定位问题出在Tarjan还是缩点还是DP。如果手算和程序输出不一致再用断点或打印中间数组的方式看是sccId错了、还是w2错了、还是f更新错了。这比直接盯着代码猜有效率得多。7. 实际测试用一组自己造的复杂数据走一遍为了让你对整条流程有一个整体观感我构造一个有环、有跨分量边、有分支的数据手动跑一遍逻辑。假设原图有6个点点权分别为1号点权52号点权63号点权74号点权85号点权96号点权10边如下1→2, 2→3, 3→1构成SCC-A3→4, 4→5, 5→44和5构成环SCC-B3→6, 6→66有自环单独成SCC-C手动缩点SCC-A包含点1、2、3权值56718SCC-B包含点4、5权值8917SCC-C包含点6权值10新图边关系A→B来自3→4A→C来自3→6C自环被忽略拓扑序可能是A→B、A→C或者A→C、A→B无所谓。DPf[A]18从A更新Bf[B]181735从A更新Cf[C]181028答案取max(18, 35, 28)35。程序输出35手算正确。你可以用这个数据测试你的代码看看结果是否符合预期。这个例子的价值在于它同时包含了“环内强连通”“环外分支”“自环”“多出边”等多个特征能同时验证Tarjan、缩点建图、自环忽略、拓扑序DP的正确性。8. 从模板题到实战缩点技巧还能用在哪P3387说到底是一个模板题它的意义不在于题目本身而在于“找出强连通分量→缩点成DAG→在DAG上做算法”这个组合拳。这个组合在竞赛和实际问题里太常用了几乎是必背技能。我遇到过好几个变种判环找最长路给一个有向图带边权求最长路径长度但图中可能存在正环。有正环意味着理论上可以无限走通常答案会变成“无限大”或需要特殊处理。如果用缩点把正环压成一个点问题就变成DAG最长路环内若有正权就只能走一遍或根据题意特殊处理复杂度降了下来。2-SAT问题2-SAT的逻辑关系图天生就是有向图求可行解时需要通过SCC缩点判断矛盾。这是Tarjan在竞赛中最重要的应用之一理解了缩点2-SAT的模板理解起来就顺了。差分约束系统差分约束建出的图也时有环但一般不会缩点因为差分约束关心的是路径上的和而环的处理方式不同。不过理解SCC对分析约束系统的可满足性有直接帮助。等价类合并在社交网络、代码依赖分析、数据血缘等应用中互相依赖的一组实体可以被视为一个整体。这种模型在很多工业级系统里也会用到SCC缩点是图数据预处理中很成熟的一环。就拿依赖分析来说你有一个模块依赖图A依赖BB依赖CC又依赖A这三个模块就在同一个强连通分量里。要部署或编译时它们必须作为一个整体打包。用Tarjan找出所有这样的依赖环再缩成整体是非常自然的建模方式。这种场景我工作后在构建系统里还真见过当时第一反应就是“这不就是P3387吗”所以你说模板题有没有用那真是有大用。8.1 从P3387到更复杂的SCC应用如果你觉得P3387太简单想进阶可以去做一下POJ 2186Popular Cows那道题是“求有多少个点能被所有点到达”做法是先缩点再统计出度为0的SCC根据出度为0的分量个数判断答案。它考察的也是缩点后的图结构分析但比P3387更抽象有助于加深对“缩点后新图性质”的理解。还有一道经典题是Luogu P2341 [HAOI2006]受欢迎的牛其实就是POJ 2186的翻译版许多博客都会拿它和P3387放在一起对比。刷完这两道你对SCC缩点的应用就基本入门了。8.2 对代码模板的长期建议我前面给的模板可以当做一个通用骨架以后遇到所有需要Tarjan缩点的题目都可以在这个模板上改。我自己的做法是把它存成代码片段snippet新建文件时直接调用然后根据题目要求改点权、边权、DP转移逻辑。长期这样做能节省大量重复劳动也能避免每次重写Tarjan时再引入低级错误。需要注意的是不同题目的点权、边权和答案要求不尽相同改动DP部分时要格外小心。比如有的题是求最小值那初始化就不能用0而是用无穷大有的题要判断是否存在负环缩点后可能还需要在SCC内部判负环。这些细节都要根据题意去调整。9. 那些年我在Tarjan上反复翻车的三个小细节写到这里我已经把P3387从原理到代码整个串了一遍。最后再分享几个我反复翻车的小细节希望能帮你减少试错成本。第一个细节是关于栈的弹出时机。Tarjan里遇到的每个SCC都要等到满足low[u] dfn[u]时一次性弹出所有属于它的节点。有些初学者在遍历边的过程中发现某个节点可以回到祖先就提前把它弹出栈这是错的。弹出操作只能在当前节点处理完所有邻接边后统一判断。第二个细节是关于DFS入口的循环。主函数里需要从1到n循环对每个未被访问的节点调用tarjan(i)。这个循环不能只调用一次tarjan(1)因为图可能不连通从1号点出发DFS覆盖不到所有节点。如果漏了这个循环未访问的节点会完全被忽略导致sccCnt统计不完整后续建图自然出错。第三个细节是关于数组大小。P3387的n和m最大1e4如果你的数组开成1e5当然更保险。但有些题目的数据范围更大比如1e5甚至1e6如果数组开小会直接RE或莫名WA。写Tarjan时养成好习惯数组大小尽量比最大值再留一点余量比如1e5的数据开2e5这样可以避免边界溢出。这三个细节看着都不起眼但每一条都让我在比赛或刷题时付出过WA的代价。写下来是想让你少走这些弯路。10. 按个人惯例留个模板扩展思路到了文章最后我不太想再总结一遍“缩点怎么做”因为前面已经把流程拆得很细了。我更想聊一个对你有长期价值的东西这个模板如何适配题目变化。P3387问的是最大点权和所以DP转移是f[v] max(f[v], f[u] w2[v])。但如果题目变成“求最小步数”你就会想环内部步数怎么算如果环是强连通分量从环的入口到出口的步数需要单独统计这就不是单纯缩点能解决的。做题时要先判断题目问的是“和”“数量”还是“可行性”再决定缩点后跑什么算法。还有一个常见变式是“缩点后求最长路但限制起点和终点必须满足某种条件”此时DP状态可能需要加一维或额外维护额外信息。模板的价值在于它把最难写的部分Tarjan稳定地封装好剩下的是灵活的DP设计。如果你把这份模板理解透并且自己动手敲过、调试过、改写过那恭喜你Tarjan这关就算真正过了。后面再遇到任何强连通分量相关的题你需要的只是把DP部分换成题目要求的逻辑而已。 强连通分量与Tarjan缩点：从洛谷P3387看DAG上DP的完整攻略
1. 这道模板题凭什么值得单独写一篇洛谷P3387的题目叫【模板】缩点我当年刷到它的时候第一反应是“这不就是数环吗”结果真正动手写才发现缩点根本不是把环找出来这么简单它背后牵扯的是一整套关于有向图强连通分量SCC的理论和一套极其优雅的Tarjan算法。如果你刚学完强连通分量想找一道题把理论和实践串起来P3387就是那个最合适的练手点。先看题目在说什么。给一张有向图每个点上带一个权值要求从任意点出发可以沿着有向边走把经过的点的权值累加一个点可以重复经过但权值只算一次问能得到的最大点权和是多少。这个约束条件很关键——“一个点可以重复经过但权值只算一次”。它意味着什么意味着如果图里存在一个环你只要进入环内就能把整个环的所有点权全部拿一遍然后从环上任意一个点离开继续往下走。环在这里就是一个“整体打包”的单位。既然是一个整体那为什么不把它压缩成一个点呢这就是缩点最朴素也最核心的动机。所以这道题有两个层面的价值。表层价值是让你学会一道经典图论题的写法深层价值是让你理解一个重要的思维范式在有向图中环是DP动态规划的破坏者而缩点是修复这个破坏的最直接手段。把有向图缩成有向无环图DAG之后所有的环都消失了于是你就可以放心大胆地在上面做拓扑序DP或记忆化搜索不会陷入循环依赖的死结。这篇文章我打算按我实际做题时的思考顺序来写先搞懂Tarjan在算什么再看缩点是怎么建的然后研究缩点后的新图怎么跑DP拿答案最后把我踩过的坑和调试思路全部倒出来。每一项都是我当时翻了很多题解才弄明白的现在整理成一份你可以直接照着一路AC的完整攻略。2. 强连通分量与Tarjan算法理解这五个核心细节就够用了2.1 强连通分量的定义以及它和“环”的区别强连通分量的定义很简洁在有向图中如果两个顶点u、v互相可达存在从u到v的路径也存在从v到u的路径那么u、v属于同一个强连通分量。一个强连通分量是极大的顶点集合集合内任意两点互相可达。注意强连通分量不一定是环。比如两个点之间有一条双向边这两个点构成一个强连通分量但它不构成一个“环”。再比如一个单独的顶点它自己到自己是可达的路径长度为0所以单点也是一个强连通分量。这一点经常被初学者忽略导致连Tarjan初始化时容易忘记每个点是独立的SCC。题目里还可能出现自环也就是点u指向u自己的边。自环不会影响Tarjan的正确性但会在缩点后的建图阶段带来一点点麻烦后面我会专门讲。总之强连通分量的本质是“互相可达的等价类”环是最典型的形态但不是唯一形态。2.2 Tarjan的两个灵魂数组dfn和lowTarjan算法基于DFS遍历核心是维护两个数组dfn[u]顶点u被DFS访问到的顺序编号也叫时间戳。low[u]顶点u能够回溯到的最早时间戳。更准确地说是从u出发通过DFS树中的子树边以及最多一条非树边返祖边能够到达的顶点其dfn的最小值。我当年学Tarjan的时候最困惑的就是low的含义。用大白话讲low[u]表示从u这个点出发在DFS的搜索过程中能绕回的最靠上的那个祖先是谁。如果u的某个后代有一条返祖边直接指到了u的祖先那u的low就会被拉高其实是拉小数值变小。如果u及其后代无论怎么走都只能到达自己人那这个连通分量就到此为止该出栈结算了。看这个细节就明白Tarjan本质上是在DFS的过程中追踪“返祖边”的能力。有向图的复杂度就在这边的方向决定了返祖边能把low拉回到什么位置。2.3 栈的作用维护“正在形成”的强连通分量Tarjan需要一个辅助栈这个栈的作用不是记录整棵DFS树的路径而是只记录当前还未被确定属于任何SCC的顶点。也就是说栈里的元素是“处理了一半、还没定性”的候选者。当一个节点的dfn访问完毕它的所有子树也递归处理完毕此时检查if (low[u] dfn[u]) { // u是某个强连通分量的根 // 从栈中弹出顶点直到弹出u为止 }为什么low[u] dfn[u]就能断定u是一个SCC的根因为如果u的low比自己小说明u能绕回到某个真正的祖先那u就不可能是这个分量的最高点它必然属于祖先所在的SCC而如果low等于dfn说明它的后代无论怎么绕都绕不出u这个范围所有能到达的点都在以u为根的DFS子树内这些点互相可达正好构成一个极大的强连通分量。这里有三个注意点栈顶弹出的顺序恰好是搜索时入栈的逆序但这不重要重要的是栈中从栈顶到u之间的所有点恰好构成一个完整的SCC。low[u] dfn[u]的判断本质上是“这个分量的根是谁”不是“这个点是不是孤立点”。一个独立的点也是SCC它的dfn和low相等会自己出栈。栈的元素是在DFS的深入过程中逐渐累积的所以递归返回时需要从栈中弹出但在递归未返回时栈顶始终是最新进入搜索的顶点。2.4 Tarjan算法的手动推演从样例到代码为了把上面这些概念串起来我手动推演一个极简的图3个点边为1→2、2→3、3→1以及3→4、4→5权值这里先不管。求SCC。从点1开始DFS访问1dfn[1]1low[1]1入栈。从1走到2dfn[2]2low[2]2入栈。从2走到3dfn[3]3low[3]3入栈。从3走到1发现1已经在栈中且正在被处理这是关键条件见下一节用dfn[1]1去更新low[3]low[3]1。3的邻接边遍历完毕递归返回到2用low[3]更新low[2]low[2]1。同理返回到1用low[2]更新low[1]low[1]1。1的邻接边还有一条到4吗没有这个例子里1到4没有边。所以1处理完毕low[1]dfn[1]从栈中弹出3、2、1这三个点构成一个SCC1,2,3。注意出栈顺序是3、2、1恰好是入栈逆序。接下来从4开始DFS访问4dfn[4]4low[4]4入栈。走到5dfn[5]5low[5]5入栈。5没有出边low[5]dfn[5]弹出5单点SCC5。回到44没有其他出边low[4]dfn[4]弹出4单点SCC4。最终得到3个SCC分别是1,2,3、4、5。这个推演过程看起来很顺但实际代码里有几个容易出错的细节下一节继续说。2.5 判断条件为什么是“在栈中”而不是“已访问”Tarjan在更新low时有一条边判断这是新手最容易写错的地方if (邻接顶点v尚未访问) { dfs(v); low[u] min(low[u], low[v]); } else if (v还在栈中) { low[u] min(low[u], dfn[v]); }这里的关键是第二个分支用dfn[v]而不是low[v]更新low。为什么因为v如果是通过返祖边到达的祖先v此时一定在栈中但v所在的SCC可能还未完全闭合。如果在这个时刻用low[v]更新可能会把某个尚在处理中的分量的low传播过来导致真正的根判断错误。而用dfn[v]更新表示的是“我能回到时间戳为dfn[v]的那个祖先”这是稳的不依赖v的子树处理状态。另外为什么已访问但已出栈的节点不能用来更新low因为一个节点一旦出栈代表它的SCC已经确定它不可能再与当前正在搜索的节点互相可达否则它们应该在同一个SCC中一起出栈。所以已出栈的节点对当前节点的low没有任何贡献。这个判断逻辑是整个Tarjan算法里最容易写挂的地方我见过不少AC代码在判断条件上写成了if (!vis[v])然后在else分支里不管是否在栈中都更新low这种写法在随机数据上可能侥幸过但在某些构造数据下会直接WA。老老实实按“在栈中”判断才能保证正确性。3. 从SCC到缩点DAG建图阶段的所有细节3.1 缩点的本质把每个SCC看成新图中的一个节点我们求完全部SCC之后要做的事情是“把每个SCC压缩成一个点”。压缩不是简单地把点合并而是要做两件事合并权值SCC内所有点的权值之和就是缩点后新节点的权值。因为在原图里只要你进入这个SCC就能把所有点的权值都走一遍。保留边关系如果原图中存在边u→v且u和v不在同一个SCC里那么在新图中从u所属的SCC连一条边到v所属的SCC。建图时最常用的方法是开辟一个染色数组color[u]表示原图点u属于哪个SCC编号。Tarjan每次找到一个完整的SCC时给这个SCC分配一个编号并把弹出的所有点的color都设置为这个编号。vectorint sccId(n 1, 0); int sccCnt 0; // Tarjan内部判断到low[u] dfn[u]时 sccCnt; while (true) { int v stk.back(); stk.pop_back(); sccId[v] sccCnt; sccWeight[sccCnt] w[v]; if (v u) break; }注意弹出时要把权值累加到一起这个sccWeight数组是后面DP的依据。3.2 遍历原图边建新图的所有注意事项染色完成之后重新遍历原图的每一条边。对每条边u→v如果sccId[u] sccId[v]说明这是SCC内部的边忽略。否则在新图中添加一条边addEdge(sccId[u], sccId[v])。这里有一个细节很多人在这个阶段会纠结“要不要去重”。其实不需要去重。两个新节点之间即使有多条边在DP时它们的意义等价于一条边不会影响结果。重边只会让邻接表多几个元素对答案没有负面影响除非你用某些特殊的算法对边的数量敏感否则直接保留即可。不过有一个例外要注意如果原图中存在自环u→u那在缩点后的新图里这个自环会被合并到SCC内部因为u和u当然属于同一个SCC所以它会在sccId[u] sccId[v]的分支里被忽略不会产生新图中的自环。3.3 新图一定是DAG——为什么这很关键缩点之后的新图必定是有向无环图。这个结论很重要因为它是后续DP能成立的基础。证明思路很直接如果新图中还存在一个环那么环上的所有新节点对应原图中的若干SCC首尾相连形成更大的互相可达关系这跟“极大强连通分量”的定义矛盾。所以不可能存在环。既然没有环就可以用拓扑序DP或记忆化搜索来求最优值。这意味着我们不用再担心环造成的无限循环或相互依赖。从任意一个SCC出发沿着边走下去一定会终止路的长度是有限的。3.4 新图的入度出度后续DP排序的依据建图时顺手统计每个新节点的入度因为之后拓扑排序会用到。这个统计不难for (int u 1; u n; u) { for (int v : originalGraph[u]) { if (sccId[u] ! sccId[v]) { newGraph[sccId[u]].push_back(sccId[v]); indeg[sccId[v]]; } } }有了入度数组跑拓扑排序时以入度为0的节点作为起点。但这里有个容易想错的地方DP的起点到底是什么题目允许从任意点出发所以入度为0的节点当然可以作为起点但并非只能从入度为0的节点出发。更准确的表述是当我们做拓扑序DP时本质上是在计算“以每个节点为结束点的最大收益”所以理论上所有节点都应该参与DP不能只从入度为0的节点开始。大部分题解的写法是遍历所有节点对每个节点做一次记忆化搜索或者按拓扑序把所有节点都处理一遍。这样才能保证最终答案覆盖从任意点出发的所有情况。3.5 一个小细节新图的根与拓扑序的等价物Tarjan在弹栈时SCC的编号是按DFS完成顺序递增的。这个顺序有一个有趣的特性SCC编号的逆序恰好是一种合法的拓扑序。这一点可以从Tarjan的递归结构推导出来一个SCC能到达的另一个SCC必然在DFS树中后访问或更晚完成。所以很多代码不写拓扑排序而是直接从sccCnt递减遍历来更新DP效果是一样的。我当时第一次看到这个结论觉得像魔法自己推演了一遍才确信。不过如果你不想依赖这个性质老老实实写一个拓扑排序也完全没问题。两种做法都会在后面的DP章节详细介绍。4. 缩点后的DP在DAG上求总权值最大的路径4.1 DP状态定义f[i]表示以节点i为终点的最大权值和缩点后的新图是一个DAG我们要在新图上找一条路径使得路径上所有点的权值之和最大。因为点权都为正题目保证点权为正数所以路径越长、覆盖的权值越多越好但这不意味着每条边都一定要走——之后的点有没有出边都不影响当前路径的收益。标准的DP状态设计是f[i]表示从某个起点出发到达节点i时能够得到的最大点权和包含节点i本身的权值。转移方程f[to] max(f[to], f[u] sccWeight[to])这个方程要从u推to就必须保证当u被用于转移时它的f值已经被彻底算好了。这正是拓扑序的必要性只有在前驱节点全部处理完之后当前节点的f值才是最终的。如果直接按节点编号顺序处理可能前面用到u时u还没被更新到最优值那后面的转移就会出错。拓扑排序或记忆化搜索都是为了解决这个顺序问题。4.2 方案一拓扑序DP的完整流程先对新图做拓扑排序得到拓扑序列数组topo。之后按拓扑序遍历每取出一个节点u就尝试用它去更新所有后继节点for (int i 1; i sccCnt; i) { int u topo[i]; for (int v : newGraph[u]) { f[v] max(f[v], f[u] sccWeight[v]); } }初始时f[i] sccWeight[i]因为可以从节点i自己出发不经过任何前驱。答案就是所有f[i]的最大值。这个写法很直观但有一个必须注意的细节拓扑排序本身的实现。新图节点的编号是1到sccCnt入度数组indeg是在建新图时统计的。用队列维护入度为0的节点每弹出u就把u的所有后继v的入度减1。这个流程非常简单不再赘述。4.3 方案二记忆化搜索的简捷之处记忆化搜索是另一种常见写法我个人觉得对于P3387这种规模的题目n和m最多1e4记忆化搜索写起来更省心因为它不需要建拓扑序也不需要开队列逻辑上更贴近“从每个起点出发搜索”的直觉int dfs(int u) { if (dp[u] ! -1) return dp[u]; dp[u] sccWeight[u]; for (int v : newGraph[u]) { dp[u] max(dp[u], sccWeight[u] dfs(v)); } return dp[u]; }然后用循环对所有节点调用dfs(i)取最大值。这个写法里dp[u]表示从u出发能获得的最大路径权值和包含u。“从任意点出发”自然就转化为“从每个可能的u出发”取最大值。因为DAG无环递归不会无限下去。记忆化搜索的缺点是递归深度可能受系统栈限制。P3387的n最大1e4加上建图数据递归深度可能接近n在部分OJ上可能会爆栈。如果遇到这种情况要么改成拓扑序DP要么用#pragma comment(linker, /STACK:1024000000)Windows或其他手段加大栈空间。4.4 两种方案选哪个我的实际取舍我个人的建议是如果是为了刷题比赛记忆化搜索更不容易写错如果是为了理解算法的本质拓扑序DP更有助于体会“DAG上DP为什么依赖拓扑序”。在洛谷P3387的数据范围下n,m ≤ 10^4递归深度一万层内存栈在很多评测机上都能扛住所以两个方案都能过。但如果你是在别的OJ上做题数据范围更大尽量用拓扑序DP图省事用记忆化搜索也没大问题只要不爆栈。我曾经在另一道题n到10^5上因为盲目用递归记忆化搜索狠狠地TLERE了一回后来改成拓扑序DP才过。那道题也让我养成一个习惯图论题涉及DP时先看一眼数据规模再决定用哪种写法。数据超过2万还带长链的优先拓扑序DP。4.5 为什么答案不是“从入度为0的点开始DP的结果”这题的题目描述是“可以任选一个点开始”很多人理解为只能从入度为0的点开始。这是不对的。假设一个点入度不为0但所有前驱节点都在一个权值很低的SCC里从它自己出发反而能绕过那些低权值的前驱获得更高的收益。举例说明新图有三个节点A、B、CA→CB→C。A的权值为1B的权值为100C的权值为1。A、B的入度都为0C的入度为2。如果只从入度为0的点出发DP初始值分别是f[A]1、f[B]100然后更新Cf[C]max(11, 1001)101。这没问题。但如果有一条边D→B且D权值为5B权值为100C权值为1。D的入度为0B的入度为1。若只从入度为0的点出发DPD→B更新后f[B]105。看起来没问题。关键在于如果B的某个入度前驱权值很大而从前驱走到B路径收益不如直接从B出发呢由于点权为正经过前驱只会让累计值变大所以入度处理一定不会让B的最佳值变小。也就是说从任意前驱走到B得到的值一定大于等于sccWeight[B]本身。因此理论上从入度为0的点出发DP并把所有入度不为0的节点也纳入转移因为它们在拓扑序中迟早会被处理到是可以覆盖所有最优解的。严谨一点说答案确实只可能从入度为0的点“开始展开”的路径中获得吗不一定因为如果某个节点i的入度全部来自权值和极小的分支但分支太小直接忽略分支从入度为0的起点出发的路径也可能不是最优。但在拓扑序DP的实现中我们并不只初始化入度为0的点而是初始化了所有节点f[i]sccWeight[i]。这样即使存在一条路径从某个节点中间开始只要中间节点本身被初始化了它就可能成为某条路径的“伪起点”。所以正确说法是所有节点都要初始化所有节点都要被处理。不要只从入度为0的节点开始推进。宁可在拓扑排序时把所有节点放入初始队列也就是把所有入度为0的节点放入队列但DP初始化所有节点然后在更新时所有节点都会被自然处理到答案取所有f的最大值。4.6 验证一个边界情况单点SCC与孤立SCC如果原图本身就是一片离散的点没有任何边那每个点单独成SCC缩点后的新图也没有边。此时f[i]初始化为sccWeight[i]就是原权值答案就是最大点权。这符合常识因为最优策略就是选一个权值最大的点直接结束。如果原图是一个大强连通分量缩点之后只有一个节点。此时新图没有边答案是整个SCC的权值之和。这也符合直觉——在这个强连通分量里你可以把所有权值都拿一遍。这些边界情况在写代码时都要想到否则容易在初始化和答案取值时出问题。5. 完整代码模板与逐段注释下面是整个P3387的C代码模板我已经把关键注释写在代码行内方便直接对照理解。这个模板是我个人惯用的写法跑过洛谷的数据稳定AC。#include bits/stdc.h using namespace std; const int MAXN 10005; int n, m; int w[MAXN]; // 原图点权 vectorint g[MAXN]; // 原图邻接表 int w2[MAXN]; // 缩点后点权 vectorint g2[MAXN]; // 缩点后邻接表 int indeg[MAXN]; // 缩点后入度 int dfn[MAXN], low[MAXN], timerCnt; int sccId[MAXN], sccCnt; int stk[MAXN], top; bool inStk[MAXN]; int f[MAXN]; // 拓扑序DP用 vectorint topo; void tarjan(int u) { dfn[u] low[u] timerCnt; stk[top] u; inStk[u] true; for (int v : g[u]) { if (!dfn[v]) { // 未访问过 tarjan(v); low[u] min(low[u], low[v]); } else if (inStk[v]) { // 已访问且在栈中 low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { sccCnt; while (true) { int x stk[top--]; inStk[x] false; sccId[x] sccCnt; w2[sccCnt] w[x]; if (x u) break; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) cin w[i]; for (int i 1; i m; i) { int u, v; cin u v; g[u].push_back(v); } // 第一遍Tarjan找SCC for (int i 1; i n; i) { if (!dfn[i]) tarjan(i); } // 缩点建图 for (int u 1; u n; u) { for (int v : g[u]) { if (sccId[u] ! sccId[v]) { g2[sccId[u]].push_back(sccId[v]); indeg[sccId[v]]; } } } // 拓扑排序 queueint q; for (int i 1; i sccCnt; i) { f[i] w2[i]; if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for (int v : g2[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } // DAG上做DP int ans 0; for (int u : topo) { ans max(ans, f[u]); for (int v : g2[u]) { f[v] max(f[v], f[u] w2[v]); } } cout ans \n; return 0; }这段代码有几个点值得再强调Tarjan里是用数组手写栈不是用STL的stack。手写栈的好处是访问栈顶元素方便弹栈逻辑也更直观性能略好。当然用std::stack也可以看个人习惯。建新图时没有去重前面说了没必要。拓扑排序用queue实现所有入度为0的节点入队。DP时按拓扑序遍历整个拓扑序列而不是只处理guaranteed起点。5.1 换成记忆化搜索的版本如果你想用记忆化搜索只需要在缩点建图之后换成下面这段逻辑int dp[MAXN]; int dfs(int u) { if (dp[u] ! -1) return dp[u]; dp[u] w2[u]; for (int v : g2[u]) { dp[u] max(dp[u], w2[u] dfs(v)); } return dp[u]; } // 在主函数中 memset(dp, -1, sizeof(dp)); int ans 0; for (int i 1; i sccCnt; i) { ans max(ans, dfs(i)); } cout ans \n;注意这个写法里dp[u] max(dp[u], w2[u] dfs(v))而不是dp[u] max(dp[u], dfs(v))。因为dfs(v)表示从v出发的最大收益不包含u的权值所以必须把u自己的权值加上。很多人第一次写容易漏掉这个w2[u]导致答案恰好少了起点的权值。5.2 两种版本的性能对比从常数上看拓扑序DP更占优因为它是纯粹的数组迭代没有递归调用开销。记忆化搜索在数据规模小的时候看不出差别但每次递归都有函数调用开销遇上1e4个节点的长链时间也完全可以接受1e4次递归每次常数操作绰绰有余。真正的问题在于递归爆栈风险而不是时间。如果你在洛谷上提交m和n最大1e4递归深度最多也是1e4通常不会爆栈。但如果你换个OJ数据范围到了1e5甚至更大那还是用拓扑序DP更稳。6. 从TLE到AC调试过程中的坑与排查思路6.1 我踩过的第一个坑Tarjan循环里误把原图的点编号当新图编号这是我第一次做P3387时犯的错误也是不少初学者的通病在缩点重建图之后下意识地拿原图点编号去更新新图的f数组。比如写完缩点后做DP时写了f[v] max(f[v], f[u] w[v])这里的u、v还在用原图节点编号而f和w2针对的是新图节点编号。这种错误跑样例可能刚好能过因为样例里的缩点关系简单加上输出恰好碰巧一致但换一组数据就直接WA。排查方法在所有涉及新图的数组操作处都确认下标是从sccId转换过来的。写代码的时候可以在建图阶段加一句assert(sccId[u] 1 sccId[u] sccCnt)帮助定位。6.2 我踩过的第二个坑low更新条件漏掉inStack判断我前面强调过else if (inStk[v]) { low[u] min(low[u], dfn[v]); }如果你写成了else { low[u] min(low[u], dfn[v]); }会把已经出栈的点也算进去。这个问题在大多数随机图上可能测不出来因为“已经出栈且存在一条边回到当前点”的情况不多见。但在严格构造的图上比如两个或多个SCC之间存在交叉引用很容易出现。我当时是自己构造了好几组图来验证的后来才彻底搞明白为什么必须是inStk判断。这里建议你实际画一画下面这个图点1、2构成一个SCC点3、4构成另一个SCC边包括1→2、2→1、2→3、3→4、4→3再加上4→1这种环外的边。如果缺少inStk判断在访问点4时发现1已经在栈外但错误地用dfn[1]更新low[4]low[4]会变成1导致4和1被错误划分进同一个SCC。这会把两个SCC错误合并进而让缩点后的图变得完全不是DAGDP结果自然也不对。6.3 我踩过的第三个坑答案取max时漏掉了单点出发的情况如果我只把f初始化为0然后从每个入度为0的节点开始更新最终答案可能漏掉“从中间某个节点出发”这种情况。虽然前面说过由于点权为正从前驱走到当前节点的收益一定不小于当前节点自身但万一中间节点没有可用的前驱能到达它呢也就是它入度为0这没问题万一它有前驱但前驱的收益因为某种原因没传过来呢拓扑排序会保证前驱先被处理前驱的f一定已经包含它的最大收益所以f[当前]一定也被更新过。但问题出在初始化上如果一开始f[i]0某个节点从自己出发的收益是0w2[i]w2[i]这没问题但如果某个节点的前驱很多按拓扑序更新下来不会漏。真正会漏的是“从自己出发”这种路径在初始化时被忽略了。稳妥的做法是初始化时f[i]w2[i]就像我的模板那样。这样每一步都包含了从自己出发的收益后面的更新只会大于等于这个值。6.4 一个隐蔽的错误拓扑排序队列初始化未包含所有入度为0的节点有时候建图时统计indeg是在原图边上循环时累加的缩点的过程中可能漏掉若干条边导致入度偏小。虽然入度偏小会让更多节点进入拓扑序队列看起来结果不会错但实际上如果漏加了某条边拓扑排序会产生一个错误的顺序某些节点的前驱没有先被处理到DP就会出问题。解决这个问题的最好方式是建新图时专门用一个独立的循环统计入度不要和Tarjan代码混在一起。我在模板里就是这么做的——先跑完Tarjan再单独遍历原图所有边来建新图和统计入度。这样树上的逻辑清晰不容易漏。另外如果新图里有重边入度会重复累加。拓扑排序时每个重边都会减一次入度因此不会死锁结果依然正确。这算是一个很幸运的性质但如果用某些“只保留一条边”的建图方式反而要小心入度统计必须和建边保持一致。6.5 性能排查为什么我的程序TLE了P3387的数据量是1e4点、1e4边理论上任何复杂度正常的算法都能过。如果你的程序跑得慢通常只有两种可能Tarjan的递归深度太深且没用编译优化不过1e4深度不至于超时只可能爆栈。你在某些循环里用了O(n²)的操作比如建新图时用set去重或者每个节点都遍历一遍sccCnt导致总复杂度变成1e8级别。1e8在1秒内对C来说很吃紧稍有不慎就TLE。我的建议是不要在新图上使用set/unordered_set去重没必要。邻接表直接push_back就行。查找操作或去重操作消耗的时间远大于重边带来的影响。6.6 万能调试手段构造小图手工验证如果WA了别急着看数据先自己构造几个小图把答案手算出来再跑程序对比。这个习惯是我刷算法题最受益的习惯之一。针对P3387建议至少构造下面几种小图一个单点、没有边看看答案是不是这个点的权值。一个长度为3的环看看答案是不是三个点权之和。一个入度为0的A连到环上环上再连到出度为0的B看看能否正确累加全部权值。两个不相连的强连通分量分别带点权看看答案是否是权值更大的那个。一条长链上每个点都是独立SCC验证DP是否按拓扑序累加。这些构造都能帮你快速定位问题出在Tarjan还是缩点还是DP。如果手算和程序输出不一致再用断点或打印中间数组的方式看是sccId错了、还是w2错了、还是f更新错了。这比直接盯着代码猜有效率得多。7. 实际测试用一组自己造的复杂数据走一遍为了让你对整条流程有一个整体观感我构造一个有环、有跨分量边、有分支的数据手动跑一遍逻辑。假设原图有6个点点权分别为1号点权52号点权63号点权74号点权85号点权96号点权10边如下1→2, 2→3, 3→1构成SCC-A3→4, 4→5, 5→44和5构成环SCC-B3→6, 6→66有自环单独成SCC-C手动缩点SCC-A包含点1、2、3权值56718SCC-B包含点4、5权值8917SCC-C包含点6权值10新图边关系A→B来自3→4A→C来自3→6C自环被忽略拓扑序可能是A→B、A→C或者A→C、A→B无所谓。DPf[A]18从A更新Bf[B]181735从A更新Cf[C]181028答案取max(18, 35, 28)35。程序输出35手算正确。你可以用这个数据测试你的代码看看结果是否符合预期。这个例子的价值在于它同时包含了“环内强连通”“环外分支”“自环”“多出边”等多个特征能同时验证Tarjan、缩点建图、自环忽略、拓扑序DP的正确性。8. 从模板题到实战缩点技巧还能用在哪P3387说到底是一个模板题它的意义不在于题目本身而在于“找出强连通分量→缩点成DAG→在DAG上做算法”这个组合拳。这个组合在竞赛和实际问题里太常用了几乎是必背技能。我遇到过好几个变种判环找最长路给一个有向图带边权求最长路径长度但图中可能存在正环。有正环意味着理论上可以无限走通常答案会变成“无限大”或需要特殊处理。如果用缩点把正环压成一个点问题就变成DAG最长路环内若有正权就只能走一遍或根据题意特殊处理复杂度降了下来。2-SAT问题2-SAT的逻辑关系图天生就是有向图求可行解时需要通过SCC缩点判断矛盾。这是Tarjan在竞赛中最重要的应用之一理解了缩点2-SAT的模板理解起来就顺了。差分约束系统差分约束建出的图也时有环但一般不会缩点因为差分约束关心的是路径上的和而环的处理方式不同。不过理解SCC对分析约束系统的可满足性有直接帮助。等价类合并在社交网络、代码依赖分析、数据血缘等应用中互相依赖的一组实体可以被视为一个整体。这种模型在很多工业级系统里也会用到SCC缩点是图数据预处理中很成熟的一环。就拿依赖分析来说你有一个模块依赖图A依赖BB依赖CC又依赖A这三个模块就在同一个强连通分量里。要部署或编译时它们必须作为一个整体打包。用Tarjan找出所有这样的依赖环再缩成整体是非常自然的建模方式。这种场景我工作后在构建系统里还真见过当时第一反应就是“这不就是P3387吗”所以你说模板题有没有用那真是有大用。8.1 从P3387到更复杂的SCC应用如果你觉得P3387太简单想进阶可以去做一下POJ 2186Popular Cows那道题是“求有多少个点能被所有点到达”做法是先缩点再统计出度为0的SCC根据出度为0的分量个数判断答案。它考察的也是缩点后的图结构分析但比P3387更抽象有助于加深对“缩点后新图性质”的理解。还有一道经典题是Luogu P2341 [HAOI2006]受欢迎的牛其实就是POJ 2186的翻译版许多博客都会拿它和P3387放在一起对比。刷完这两道你对SCC缩点的应用就基本入门了。8.2 对代码模板的长期建议我前面给的模板可以当做一个通用骨架以后遇到所有需要Tarjan缩点的题目都可以在这个模板上改。我自己的做法是把它存成代码片段snippet新建文件时直接调用然后根据题目要求改点权、边权、DP转移逻辑。长期这样做能节省大量重复劳动也能避免每次重写Tarjan时再引入低级错误。需要注意的是不同题目的点权、边权和答案要求不尽相同改动DP部分时要格外小心。比如有的题是求最小值那初始化就不能用0而是用无穷大有的题要判断是否存在负环缩点后可能还需要在SCC内部判负环。这些细节都要根据题意去调整。9. 那些年我在Tarjan上反复翻车的三个小细节写到这里我已经把P3387从原理到代码整个串了一遍。最后再分享几个我反复翻车的小细节希望能帮你减少试错成本。第一个细节是关于栈的弹出时机。Tarjan里遇到的每个SCC都要等到满足low[u] dfn[u]时一次性弹出所有属于它的节点。有些初学者在遍历边的过程中发现某个节点可以回到祖先就提前把它弹出栈这是错的。弹出操作只能在当前节点处理完所有邻接边后统一判断。第二个细节是关于DFS入口的循环。主函数里需要从1到n循环对每个未被访问的节点调用tarjan(i)。这个循环不能只调用一次tarjan(1)因为图可能不连通从1号点出发DFS覆盖不到所有节点。如果漏了这个循环未访问的节点会完全被忽略导致sccCnt统计不完整后续建图自然出错。第三个细节是关于数组大小。P3387的n和m最大1e4如果你的数组开成1e5当然更保险。但有些题目的数据范围更大比如1e5甚至1e6如果数组开小会直接RE或莫名WA。写Tarjan时养成好习惯数组大小尽量比最大值再留一点余量比如1e5的数据开2e5这样可以避免边界溢出。这三个细节看着都不起眼但每一条都让我在比赛或刷题时付出过WA的代价。写下来是想让你少走这些弯路。10. 按个人惯例留个模板扩展思路到了文章最后我不太想再总结一遍“缩点怎么做”因为前面已经把流程拆得很细了。我更想聊一个对你有长期价值的东西这个模板如何适配题目变化。P3387问的是最大点权和所以DP转移是f[v] max(f[v], f[u] w2[v])。但如果题目变成“求最小步数”你就会想环内部步数怎么算如果环是强连通分量从环的入口到出口的步数需要单独统计这就不是单纯缩点能解决的。做题时要先判断题目问的是“和”“数量”还是“可行性”再决定缩点后跑什么算法。还有一个常见变式是“缩点后求最长路但限制起点和终点必须满足某种条件”此时DP状态可能需要加一维或额外维护额外信息。模板的价值在于它把最难写的部分Tarjan稳定地封装好剩下的是灵活的DP设计。如果你把这份模板理解透并且自己动手敲过、调试过、改写过那恭喜你Tarjan这关就算真正过了。后面再遇到任何强连通分量相关的题你需要的只是把DP部分换成题目要求的逻辑而已。