判断图中是否有环是拓扑排序的前提：有环则无法拓扑排序；可用Kahn算法（入度统计）或DFS（标记white/gray/black）检测，若最终输出节点数≠总节点数或DFS遇gray节点即存在环。
怎么判断图里有没有环，再决定能不能拓扑排序
拓扑排序只对有向无环图（DAG）有效。如果图里存在环，topological_sort 就没意义——你根本找不到一个“所有依赖都已满足”的起点。所以别急着排，先用 DFS 或入度统计法验环。
常见错误现象：std::queue 空了但还有节点没输出，说明图里有环；或者 DFS 回溯时发现正在访问中的节点又被访问了一次（即遇到灰色节点）。
- 推荐用 Kahn 算法（基于入度）同步验环：最终输出节点数 ≠ 总节点数 → 有环
- DFS 实现要注意状态标记：未访问（white）、访问中（gray）、已访问（black），遇到 gray 就是环
- 别用
std::vector<std::vector<int>>存稠密图还跑 DFS，递归太深可能栈溢出；稀疏图优先用邻接表 + 迭代 BFS
Kahn 算法实现拓扑排序的最小可行代码
这是最稳、最容易调试的写法，适合处理模块依赖、构建顺序、任务调度等真实场景。
关键不是“怎么写完”，而是“怎么保证每步不漏”：建图 → 统计入度 → 入度为 0 的进队 → 每次取一个，更新邻居入度，再推新零入度节点。
立即学习“C++免费学习笔记（深入）”；
- 图用
std::vector<std::vector<int>>存邻接表，节点编号从 0 开始最省事 - 入度数组用
std::vector<int>，初始化为 0，遍历边时自增 - 用
std::queue<int>，不用std::stack—— BFS 顺序更符合“依赖先行”的直觉 - 示例片段：
std::vector<int> indeg(n, 0); for (auto& e : edges) indeg[e[1]]++; std::queue<int> q; for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); res.push_back(u); for (int v : graph[u]) { if (--indeg[v] == 0) q.push(v); } }
std::sort 不能替代拓扑排序，哪怕你重载了比较函数
有人试图用 std::sort 加自定义 comp 来“模拟”拓扑序，比如写 comp(a, b) { return !can_reach(b, a); } —— 这在绝大多数情况下会崩。
原因很简单：std::sort 要求比较函数满足严格弱序（strict weak ordering），而“a 依赖于 b”这种关系既不自反、也不传递（A→B、B→C 不一定推出 A→C 在路径上直接存在），更别说 transitivity 和 irreflexivity 无法保证。
- 运行时可能触发
error: invalid comparator（GCC 下 assertion 失败） - 即使侥幸跑过，结果也可能是错的：两个无依赖关系的节点被强行排定先后，破坏并行性语义
- 性能上也不划算：每次比较都要做一次可达性 DFS/BFS，复杂度飙升到 O(V·(V+E))
多个合法拓扑序时，如何固定输出结果
当存在多个入度为 0 的节点时，Kahn 算法默认用 std::queue，顺序取决于插入顺序（通常是输入顺序或小编号优先）。但如果你需要确定性结果（比如测试断言、CI 构建可重现），就得控制这个“选择策略”。
注意：这不是“优化”，而是避免非预期行为。比如 C++ 模块依赖解析中，两个无依赖的头文件谁先被 include，会影响宏定义可见性。
- 用
std::priority_queue<int, std::vector<int>, std::greater<int>>替换std::queue，就能让编号小的节点永远优先 - 如果依赖名是字符串，就建映射表，把名字转成稳定整数 ID 再进堆
- 别用
std::set动态维护候选集——虽然逻辑清晰，但常数大，且容易因迭代器失效出错
