kahn算法用std::vector存邻接表和入度数组、std::queue实现bfs拓扑排序，需初始化入度为0、正确更新邻接点入度、处理重边自环并校验结果长度是否等于节点数。
怎么用 std::vector 和 std::queue 手写 Kahn 算法
拓扑排序在 C++ 里没有标准库函数直接调用，得自己实现；Kahn 算法是最稳妥、最易调试的选择。它依赖入度统计 + BFS，不递归，不怕深栈，也避免了 DFS 实现中容易漏掉的环检测逻辑错位问题。
常见错误现象：std::queue 里塞了节点但没更新邻接点入度，导致后续节点永远进不了队列；或者入度数组没初始化为 0，出现随机值导致跳过合法节点。
- 先用
std::vector<:vector>></:vector>存邻接表，别用std::map或std::unordered_map—— 节点编号通常是连续整数，下标访问更快也更稳 - 入度数组大小必须和节点总数一致（比如 n 个节点就开
std::vector<int>(n, 0)</int>），别按边数或 vector.size() 推断 - 遍历所有边时，对每个
u → v，执行indeg[v]++；千万别写成indeg[u]++ - 初始把所有
indeg[i] == 0的i塞进std::queue，注意节点编号是否从 0 开始（多数题是 0-based）
DFS 版拓扑排序为什么容易出错
DFS 版本质是后序遍历 + 检测回边，但 C++ 里手动维护「当前路径栈」状态稍不注意就会崩：要么漏判环，要么把合法反向边当环，要么结果顺序颠倒。
典型翻车场景：用一个 std::vector<bool></bool> 表示「已访问」，但没区分「全局访问过」和「本次 DFS 正在路径中」—— 这会导致环检测失效，返回假阳性或漏环。
立即学习“C++免费学习笔记（深入）”；
- 必须用三种状态：未访问（
false）、访问中（true，在当前 DFS 栈上）、已访问完成（单独用另一个std::vector<bool></bool>或用 int 数组编码） - 递归返回前才把节点加到结果前端（比如
result.insert(result.begin(), u)），别用push_back再 reverse —— 多一次遍历，且容易忘 - 一旦发现邻接点状态是「访问中」，立刻返回 false，整个图有环；别只打个日志就继续跑
- 如果图不连通，要遍历所有节点作为 DFS 起点，不能只从 0 开始
std::priority_queue 能不能用来做字典序最小拓扑序
能，但仅限于要求「每次选入度为 0 中编号最小的节点」这种明确规则时。它不是拓扑排序的必需组件，而是特定需求下的替换策略。
性能影响明显：普通 std::queue 是 O(1) 入队出队，而 std::priority_queue 是 O(log n)，整体会从 O(V+E) 变成 O((V+E) log V)；小数据看不出，节点超 1e4 就得掂量。
- 声明要带比较器：
std::priority_queue<int std::vector>, std::greater<int>></int></int>，否则默认大根堆，取出来的是最大编号 - 入队时机和 Kahn 完全一致：每当某个节点入度减到 0，就 push 进去
- 出队后仍需遍历其所有邻接点并更新入度，逻辑不变，只是选起点的方式变了
- 如果节点编号不是整数（比如 string），就得自定义比较器，这时得权衡：手写 map 映射还是换回 vector 下标
输入含重边或自环时怎么防崩
题目给的边列表经常不干净：可能有重复边 u→v 出现两次，也可能有 u→u。这些会直接破坏 Kahn 算法的入度统计和环判定逻辑。
常见错误现象：入度被重复加，导致本该入队的节点迟迟不入队；或者自环让入度永远 ≥1，误判为有环。
- 读边时先用
std::set<:pair int>></:pair>去重，再转邻接表；别图省事跳过去重 - 遇到
u == v（自环），直接报错或跳过，并标记图非法；C++ 拓扑排序的前提是 DAG，自环即非 DAG - 如果题目允许重边但要求计数（比如带权），那入度就得用
int累加，但判断入度为 0 时仍只看是否等于 0，不是是否「首次归零」 - 输出结果前，检查最终拓扑序列长度是否等于节点总数；不等就说明有环（包括自环或强连通分量）
真正麻烦的不是写法，而是边界：节点编号是否连续、图是否一定连通、输入有没有空行或非法字符。这些地方一松懈，std::vector 就越界，std::queue 就空取，结果对小样例没问题，一交就 RE 或 WA。
