拓扑排序失败时dfs返回false，本质是检测到有向环：节点状态分0（未访问）、1（访问中）、2（已访问），若dfs中再次遇到状态为1的节点，立即返回false；外层需遍历所有节点并仅对状态0调用dfs，避免误判或栈溢出。
拓扑排序失败时 dfs 返回 false 的判断逻辑怎么写？
拓扑排序失败，本质是图中存在环。DFS 版本必须靠节点状态区分“当前递归栈中正在访问”和“已彻底访问完毕”，否则无法识别回边构成的环。
每个节点需维护三种状态：unvisited（未访问）、visiting（在当前 DFS 路径中）、visited（已回溯完成）。一旦在 visiting 状态下再次遇到同一节点，立刻返回 false。
-
visiting状态必须在进入递归前设为 true，回溯前设为 false —— 不能只靠函数调用栈隐含判断 - 若仅用 bool 数组标记“是否访问过”，会把跨路径的重复访问误判为环
- 状态数组类型推荐
vector<int></int>：0=unvisited，1=visiting，2=visited，避免布尔翻转歧义
std::stack<int></int> 还是 vector<int></int> 存结果更稳妥？
DFS 拓扑序本质是“后序遍历逆序”，即节点在所有邻接点都处理完后才入结果容器。用 std::stack 是直觉选择，但实际更推荐 vector + push_back + 最终 reverse。
-
stack不支持随机访问，调试时无法直接打印中间状态 - 某些编译器对
stack的内存分配策略不如vector可控，尤其节点数上万时 - 用
vector可在 DFS 中直接result.push_back(u)，最后reverse(result.begin(), result.end())，语义清晰且无额外开销
邻接表用 vector<vector>></vector> 还是 vector<unordered_set>></unordered_set>？
取决于是否需要去重或频繁查边存在性。拓扑排序本身不要求边唯一，但重复边会导致状态误判或冗余递归。
- 输入数据若可能含重边，用
unordered_set可自动去重，避免多次访问同一邻居 - 若图稀疏且顶点编号连续（如 0~n-1），
vector<vector>></vector>内存局部性更好，cache 友好 - 注意：用
set会引入 log n 开销，无必要；unordered_set均摊 O(1)，但构造时需预留桶数（reserve）防 rehash 影响性能
主函数里调用 dfs(u) 前为什么必须检查 state[u] == unvisited？
因为 DFS 是从任意未访问节点启动的，不是所有节点都能从一个起点遍历到（有向图可能含多个弱连通分量）。漏掉检查会导致对 visiting 或 visited 节点重复调用，轻则逻辑错乱，重则栈溢出或越界访问。
- 必须在外层循环中遍历所有节点，对每个
state[u] == 0的节点才调用dfs(u) - 不能只从入度为 0 的点开始——那只是 Kahn 算法的思路，DFS 版本不依赖入度信息
- 若跳过检查，遇到
visiting节点会触发环判定，导致本不该失败的 DAG 被误判
真正容易被忽略的是状态数组的初始化和复用：多组测试时若忘记重置 state 数组，前一组的 visited 状态会污染后一组；而 visiting 状态若没在异常退出路径中手动清理，也会导致后续判断失真。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
