应设三态：UNVISITED（未访问）、ON_PATH（当前路径中）、VISITED（已访问完毕）；仅当邻接点状态为ON_PATH时判定成环，避免布尔数组对跨分支后向边的误判。
DFS递归中节点的三种状态怎么设才不漏判环
拓扑排序用DFS检测环，关键不在递归本身，而在如何标记节点状态。只用 visited 布尔数组会误判后向边为环——比如从 A→B→C，再从 D→B，B 已访问但并非在当前路径上，此时不能断定有环。
必须区分「全局已访问」和「当前DFS路径中正在访问」。推荐三态枚举：
-
UNVISITED（0）：从未入栈也未出栈 -
ON_PATH（1）：已入栈、尚未回溯（即在当前递归路径上） -
VISITED（2）：已完整遍历并出栈（安全，可跳过）
遇到状态为 ON_PATH 的邻接点，立刻返回环存在；遇到 VISITED 直接跳过；只有 UNVISITED 才继续递归。
递归函数返回值设计：bool 还是 void
用 bool 返回值最直接——成功完成当前子图遍历则返回 true，中途发现环则立即返回 false 并逐层透传。避免用全局标志位或异常，否则控制流易失控。
立即学习“C++免费学习笔记（深入）”；
典型结构如下：
bool dfs(int u) {
state[u] = ON_PATH;
for (int v : graph[u]) {
if (state[v] == ON_PATH) return false; // 环
if (state[v] == UNVISITED && !dfs(v)) return false;
}
state[u] = VISITED;
result.push_back(u); // 逆序入栈，最后 reverse
return true;
}
注意：result 是 vectorreverse(result.begin(), result.end()) 才是合法拓扑序。
邻接表构建时边方向别反了
拓扑排序要求：若存在边 u → v，则 u 必须排在 v 前面。这意味着图中每条边代表「依赖关系」：u 依赖 v，即 v 是 u 的前置任务？不对——常见错误就在这里。
正确理解是：边 u → v 表示「u 必须在 v 之前完成」，即 v 依赖 u。因此建图时，若题目说“任务 A 必须在任务 B 之前”，应添加边 A → B。
验证方法：跑完拓扑序后，对每条原始边 u → v，检查 pos[u] < pos[v]（pos[x] 是 x 在结果中的下标）。不满足则建图方向反了。
空图、孤立点、多连通分量怎么保证全遍历
DFS递归版默认只从起点出发，若图不连通会漏掉其他连通分量里的节点。必须对每个 UNVISITED 节点都调用一次 dfs()。
常见疏忽点：
- 节点编号不连续（如输入含 0, 2, 5），不能只遍历
0到n-1，得用实际出现过的节点集 - 孤立点（无入边也无出边）也要进结果，且状态会从
UNVISITED→ON_PATH→VISITED，不会被跳过 - 主循环中一旦某次
dfs(u)返回false，应立刻终止并返回失败，不要继续遍历其他节点
初始化 state 数组时，大小要覆盖所有可能出现的节点编号最大值，或用 unordered_map<int, int> 动态管理更稳妥。
