Kosaraju算法通过两次DFS求强连通分量：第一次在原图DFS记录节点退出顺序（后序），第二次在转置图中按该顺序逆序DFS，每次新遍历到的节点集即为一个SCC。
第一次DFS必须记录“退出顺序”，不是访问顺序
很多人写 dfs1 时只记了访问时间（disc_time），但 Kosaraju 要的是节点递归返回时的“完成时间”或“退出时间”。这个顺序本质是后序遍历的结果，决定了第二次 DFS 的起点优先级。
常见错误是把 order.push_back(v) 放在进入函数开头，正确位置是在所有邻接点遍历完、即将返回前：
void dfs1(int v) {
vis[v] = true;
for (int u : graph[v]) {
if (!vis[u]) dfs1(u);
}
order.push_back(v); // ✅ 这里才是退出时刻
}
- 用
vector存就直接reverse(order.begin(), order.end())得到逆序；更常用的是用stack，弹出即自然逆序 - 如果图不连通，必须对每个未访问节点都调用
dfs1，不能只从 0 或 1 开始一次就完事
反向图构建必须严格翻转每条有向边
所谓“反向图”不是简单交换邻接表索引，而是对原图中每条 u → v，在新图中添加 v → u。如果用邻接表存储，别漏掉任何一条边；如果用邻接矩阵，要显式转置（rev_graph[v][u] = graph[u][v]）。
容易踩的坑：
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 原图含重边或自环？反向图也要保留——Kosaraju 不要求去重
- 用
vector<vector<int>>构建反向图时，别忘了先 resize 到n+1，否则rev_graph[v].push_back(u)可能越界 - 若原图用 1-indexed，反向图也必须保持一致，否则
dfs2会访问非法下标
第二次DFS必须按退出时间逆序遍历，且只跑未访问节点
第二次 DFS 的入口节点顺序不能是 for (int i = 0; i ，而必须是 <code>for (int i = order.size()-1; i >= 0; i--) 或等价地 while (!stk.empty()) { v = stk.top(); stk.pop(); if (!vis2[v]) dfs2(v); }。
关键逻辑在于：只有当 !vis2[v] 时才启动新一次 dfs2，每次成功进入的 dfs2(v) 所访问到的所有节点，才属于同一个 SCC。
- 不要在
dfs2内部重置全局计数器——SCC 编号应由外层循环控制 -
dfs2遍历的是反向图rev_graph，不是原图graph；边方向错了，整个 SCC 就散了 - 性能上，两次 DFS 各跑一遍所有点和边，总复杂度稳定
O(V + E)，不依赖栈深度或常数因子
调试时最该检查的三个变量
当输出 SCC 数量不对、或某些点被错误归类，优先盯住这三个地方：
-
order是否包含全部n个节点？缺一个就意味第一次 DFS 漏点了 -
rev_graph的边数是否等于原图graph的边数？不等说明翻转漏边 - 第二次 DFS 中，
vis2数组是否初始化为false？没清零会导致跳过合法起点
强连通分量本身不输出拓扑序，但 Kosaraju 给出的 SCC 编号顺序，恰好对应原图 SCC 缩点后的逆拓扑序——这点常被忽略，但在后续做 DAG 动态规划时非常有用。
