不能直接在原图上dp，因环导致状态转移不成立；缩点后得dag，须用tarjan/kosaraju，建图时跳过自环，再拓扑序dp或记忆化dfs。
缩点后直接在 DAG 上跑记忆化 DFS 或拓扑序 DP，别用普通 DFS 暴搜——会重复计算、栈溢出、漏更新。
为什么不能直接在原图上 DP
原图有环，dp[u] 依赖 dp[v]，dp[v] 又可能依赖 dp[u]，状态转移不成立。缩点后每个 SCC 变成一个节点，边只从编号小的 SCC 指向编号大的（或按拓扑序定向），环被彻底消除。
常见错误现象：dp[u] = max(dp[u], dp[v] + weight[u]) 在未保证 v 已算完时就调用，结果全为 0 或随机值；或者递归爆栈（尤其链式 SCC 较深时）。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 缩点必须用
tarjan或kosaraju，不能靠手动合并——漏判一个反向边就破坏 DAG 结构 -
weight[i]是第i个 SCC 内所有点权之和，不是点个数（除非题设宝石数=1） - 缩点建新图时，要跳过
set[u] == set[v]的自环边，否则 DAG 变回带环图
两种安全的 DAG 动态规划写法
推荐优先用拓扑排序 + 顺序 DP，稳定性高；记忆化 DFS 更简洁但需确保递归深度可控。
-
拓扑排序法：先求入度数组
indeg[i]，用队列推入所有indeg[i] == 0的 SCC；每次取出u，遍历其邻接点v，执行dp[v] = max(dp[v], dp[u] + weight[v])，然后indeg[v]--；入度归零即刻入队 -
记忆化 DFS 法：对每个 SCC 节点
u，若dp[u]已算过直接返回；否则初始化dp[u] = weight[u]，再对每个邻接v更新dp[u] = max(dp[u], dfs(v) + weight[u]) - 两者都要求新图用
vector<vector>></vector>存邻接表，不能用 map 或 unordered_map ——常数大、易超时
缩点建图时最常踩的三个坑
这三处写错，后面 DP 全白做。
-
tarjan中判断是否在栈内必须用instack[v]，不能用dfn[v]是否为 0 ——后者只能判是否访问过，无法区分已出 SCC 和仍在栈中 - 建缩点边时，必须写
if (set[u] != set[v]) edge2[set[u]].push_back(set[v])；漏掉!=判断会导致自环，DAG 崩溃 - SCC 编号从 1 开始（如
scccnt++后赋值），但数组下标习惯从 0 开始——weight[set[u]]里的set[u]若从 0 开始，weight数组大小就得开到scccnt+1，否则越界
真正麻烦的从来不是 DP 本身，而是缩点过程中 dfn/low 的维护顺序、栈弹出边界、以及新图边方向是否真无环——建议每次缩点后打印前几条边，肉眼确认没有 u→u 或 3→2 这类逆拓扑边。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
