企业官网建设流程全解析

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和low

Tarjan算法基于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子树内，这些点互相可达，正好构成一个极大的强连通分量。

这里有三个注意点：

1. 栈顶弹出的顺序恰好是搜索时入栈的逆序，但这不重要，重要的是栈中从栈顶到u之间的所有点，恰好构成一个完整的SCC。
2. low[u] == dfn[u]的判断本质上是“这个分量的根是谁”，不是“这个点是不是孤立点”。一个独立的点也是SCC，它的dfn和low相等，会自己出栈。
3. 栈的元素是在DFS的深入过程中逐渐累积的，所以递归返回时需要从栈中弹出，但在递归未返回时，栈顶始终是最新进入搜索的顶点。

2.4 Tarjan算法的手动推演：从样例到代码

为了把上面这些概念串起来，我手动推演一个极简的图：3个点，边为1→2、2→3、3→1，以及3→4、4→5，权值这里先不管。求SCC。

从点1开始DFS：

• 访问1，dfn[1]=1，low[1]=1，入栈。
• 从1走到2，dfn[2]=2，low[2]=2，入栈。
• 从2走到3，dfn[3]=3，low[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，这三个点构成一个SCC（1,2,3）。

注意出栈顺序是3、2、1，恰好是入栈逆序。

接下来从4开始DFS：

• 访问4，dfn[4]=4，low[4]=4，入栈。
• 走到5，dfn[5]=5，low[5]=5，入栈。
• 5没有出边，low[5]==dfn[5]，弹出5，单点SCC（5）。
• 回到4，4没有其他出边，low[4]==dfn[4]，弹出4，单点SCC（4）。

最终得到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压缩成一个点”。压缩不是简单地把点合并，而是要做两件事：

1. 合并权值：SCC内所有点的权值之和，就是缩点后新节点的权值。因为在原图里，只要你进入这个SCC，就能把所有点的权值都走一遍。
2. 保留边关系：如果原图中存在边u→v，且u和v不在同一个SCC里，那么在新图中，从u所属的SCC连一条边到v所属的SCC。

建图时最常用的方法是开辟一个染色数组color[u]，表示原图点u属于哪个SCC编号。Tarjan每次找到一个完整的SCC时，给这个SCC分配一个编号，并把弹出的所有点的color都设置为这个编号。

vector<int> 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）上因为盲目用递归记忆化搜索狠狠地TLE+RE了一回，后来改成拓扑序DP才过。那道题也让我养成一个习惯：图论题涉及DP时，先看一眼数据规模再决定用哪种写法。数据超过2万还带长链的，优先拓扑序DP。

4.5 为什么答案不是“从入度为0的点开始DP的结果”

这题的题目描述是“可以任选一个点开始”，很多人理解为只能从入度为0的点开始。这是不对的。假设一个点入度不为0，但所有前驱节点都在一个权值很低的SCC里，从它自己出发反而能绕过那些低权值的前驱，获得更高的收益。

举例说明：

• 新图有三个节点A、B、C，A→C，B→C。
• A的权值为1，B的权值为100，C的权值为1。
• A、B的入度都为0，C的入度为2。

如果只从入度为0的点出发DP，初始值分别是f[A]=1、f[B]=100，然后更新C：f[C]=max(1+1, 100+1)=101。这没问题。

但如果有一条边D→B，且D权值为5，B权值为100，C权值为1。D的入度为0，B的入度为1。若只从入度为0的点出发DP，D→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]; // 原图点权 vector<int> g[MAXN]; // 原图邻接表 int w2[MAXN]; // 缩点后点权 vector<int> 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用 vector<int> 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]]++; } } } // 拓扑排序 queue<int> 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; }

这段代码有几个点值得再强调：

1. Tarjan里是用数组手写栈，不是用STL的stack。手写栈的好处是访问栈顶元素方便，弹栈逻辑也更直观，性能略好。当然用std::stack也可以，看个人习惯。
2. 建新图时没有去重，前面说了，没必要。
3. 拓扑排序用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错误合并，进而让缩点后的图变得完全不是DAG，DP结果自然也不对。

6.3 我踩过的第三个坑：答案取max时漏掉了单点出发的情况

如果我只把f初始化为0，然后从每个入度为0的节点开始更新，最终答案可能漏掉“从中间某个节点出发”这种情况。虽然前面说过，由于点权为正，从前驱走到当前节点的收益一定不小于当前节点自身，但万一中间节点没有可用的前驱能到达它呢？也就是它入度为0，这没问题；万一它有前驱，但前驱的收益因为某种原因没传过来呢？拓扑排序会保证前驱先被处理，前驱的f一定已经包含它的最大收益，所以f[当前]一定也被更新过。

但问题出在初始化上：如果一开始f[i]=0，某个节点从自己出发的收益是0+w2[i]=w2[i]，这没问题；但如果某个节点的前驱很多，按拓扑序更新下来不会漏。真正会漏的是“从自己出发”这种路径在初始化时被忽略了。

稳妥的做法是初始化时f[i]=w2[i]，就像我的模板那样。这样每一步都包含了从自己出发的收益，后面的更新只会大于等于这个值。

6.4 一个隐蔽的错误：拓扑排序队列初始化未包含所有入度为0的节点

有时候建图时统计indeg是在原图边上循环时累加的，缩点的过程中可能漏掉若干条边，导致入度偏小。虽然入度偏小会让更多节点进入拓扑序队列，看起来结果不会错，但实际上如果漏加了某条边，拓扑排序会产生一个错误的顺序，某些节点的前驱没有先被处理到，DP就会出问题。

解决这个问题的最好方式是：建新图时专门用一个独立的循环统计入度，不要和Tarjan代码混在一起。我在模板里就是这么做的——先跑完Tarjan，再单独遍历原图所有边来建新图和统计入度。这样树上的逻辑清晰，不容易漏。

另外，如果新图里有重边，入度会重复累加。拓扑排序时每个重边都会减一次入度，因此不会死锁，结果依然正确。这算是一个很幸运的性质，但如果用某些“只保留一条边”的建图方式，反而要小心入度统计必须和建边保持一致。

6.5 性能排查：为什么我的程序TLE了

P3387的数据量是1e4点、1e4边，理论上任何复杂度正常的算法都能过。如果你的程序跑得慢，通常只有两种可能：

1. Tarjan的递归深度太深且没用编译优化，不过1e4深度不至于超时，只可能爆栈。
2. 你在某些循环里用了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号点权5
• 2号点权6
• 3号点权7
• 4号点权8
• 5号点权9
• 6号点权10

边如下：

• 1→2, 2→3, 3→1（构成SCC-A）
• 3→4, 4→5, 5→4（4和5构成环SCC-B）
• 3→6, 6→6（6有自环，单独成SCC-C）

手动缩点：

• SCC-A包含点1、2、3，权值=5+6+7=18
• SCC-B包含点4、5，权值=8+9=17
• SCC-C包含点6，权值=10

新图边关系：

• A→B（来自3→4）
• A→C（来自3→6）
• C自环被忽略

拓扑序可能是A→B、A→C，或者A→C、A→B，无所谓。

DP：

• f[A]=18
• 从A更新B：f[B]=18+17=35
• 从A更新C：f[C]=18+10=28

答案取max(18, 35, 28)=35。

程序输出35，手算正确。你可以用这个数据测试你的代码，看看结果是否符合预期。

这个例子的价值在于它同时包含了“环内强连通”“环外分支”“自环”“多出边”等多个特征，能同时验证Tarjan、缩点建图、自环忽略、拓扑序DP的正确性。

8. 从模板题到实战：缩点技巧还能用在哪

P3387说到底是一个模板题，它的意义不在于题目本身，而在于“找出强连通分量→缩点成DAG→在DAG上做算法”这个组合拳。这个组合在竞赛和实际问题里太常用了，几乎是必背技能。

我遇到过好几个变种：

1. 判环找最长路：给一个有向图，带边权，求最长路径长度，但图中可能存在正环。有正环意味着理论上可以无限走，通常答案会变成“无限大”或需要特殊处理。如果用缩点把正环压成一个点，问题就变成DAG最长路，环内若有正权就只能走一遍（或根据题意特殊处理），复杂度降了下来。

2. 2-SAT问题：2-SAT的逻辑关系图天生就是有向图，求可行解时需要通过SCC缩点判断矛盾。这是Tarjan在竞赛中最重要的应用之一，理解了缩点，2-SAT的模板理解起来就顺了。

3. 差分约束系统：差分约束建出的图也时有环，但一般不会缩点，因为差分约束关心的是路径上的和，而环的处理方式不同。不过理解SCC对分析约束系统的可满足性有直接帮助。

4. 等价类合并：在社交网络、代码依赖分析、数据血缘等应用中，互相依赖的一组实体可以被视为一个整体。这种模型在很多工业级系统里也会用到，SCC缩点是图数据预处理中很成熟的一环。

就拿依赖分析来说，你有一个模块依赖图，A依赖B，B依赖C，C又依赖A，这三个模块就在同一个强连通分量里。要部署或编译时，它们必须作为一个整体打包。用Tarjan找出所有这样的依赖环，再缩成整体，是非常自然的建模方式。这种场景我工作后在构建系统里还真见过，当时第一反应就是“这不就是P3387吗”，所以你说模板题有没有用，那真是有大用。

8.1 从P3387到更复杂的SCC应用

如果你觉得P3387太简单，想进阶，可以去做一下POJ 2186（Popular 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部分换成题目要求的逻辑而已。