拓扑排序仅适用于有向无环图（DAG），核心算法为Kahn或DFS；Kahn更推荐，需统计入度、用队列处理入度为0的节点，最终检查结果长度是否等于节点数。
拓扑排序的本质是 DAG 的线性化，不是所有图都能做
只有有向无环图（DAG）才能进行拓扑排序；如果图中存在环，topological_sort 无解。C++ 标准库不提供现成函数，必须手写——核心是基于入度的 Kahn 算法或 DFS 回溯。Kahn 更直观、易调试，推荐优先用。
Kahn 算法：用队列维护当前入度为 0 的节点
关键在于建图时统计每个节点的入度，然后把所有入度为 0 的节点入队。每次取出一个节点，把它指向的所有邻居入度减 1，若减到 0 就入队。最终结果数组长度若小于节点总数，说明有环。
常见错误现象：std::queue 忘记初始化、邻接表用 vector<vector>></vector> 但索引越界、入度数组未清零。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 用
vector<int> indegree(n, 0)</int>显式初始化入度数组，别依赖默认值 - 邻接表用
vector<vector>> graph(n)</vector>，添加边时只做graph[u].push_back(v)，同时indegree[v]++ - 队列用
queue<int></int>，存节点编号而非指针或迭代器 - 最后检查
result.size() != n时直接返回空vector或抛异常，不要静默截断
vector<int> topologicalSort(int n, const vector<vector<int>>& edges) {
vector<vector<int>> graph(n);
vector<int> indegree(n, 0);
for (auto& e : edges) {
int u = e[0], v = e[1];
graph[u].push_back(v);
indegree[v]++;
}
queue<int> q;
for (int i = 0; i < n; ++i)
if (indegree[i] == 0) q.push(i);
vector<int> result;
while (!q.empty()) {
int u = q.front(); q.pop();
result.push_back(u);
for (int v : graph[u]) {
if (--indegree[v] == 0) q.push(v);
}
}
return result.size() == n ? result : vector<int>();
}
DFS 实现要注意递归状态标记，避免误判环
DFS 版本需要三种状态标记：0（未访问）、1（正在递归栈中）、2（已访问完成）。遇到状态为 1 的节点即说明成环。结果需逆序输出，因为叶子节点先完成回溯。
容易踩的坑：
- 用
vector<bool></bool>存状态？它不是真正的容器，operator[]返回代理对象，可能引发未定义行为；改用vector<int></int>或vector<char></char> - 忘记在进入 DFS 前设
state[u] = 1，或在 return 前没设state[u] = 2 - 结果 vector 没 reverse，导致顺序反了
实际使用时得考虑输入格式和节点编号范围
很多题目给的是边列表，节点编号未必从 0 连续；也可能含重复边或自环。Kahn 算法对重复边敏感（会导致入度多加），自环则直接让入度永远 >0。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 预处理边列表：用
set<pair>></pair>去重，再过滤掉u == v的自环 - 若节点编号稀疏（如 10000 个节点但只出现 100 个 ID），先离散化映射到
[0, k) - 性能上，Kahn 是
O(V + E)，DFS 也是，但 Kahn 缓存友好、无递归开销；DFS 在深图中可能栈溢出
真正卡住人的往往不是算法逻辑，而是建图前没校验输入、状态数组大小配错、或者把有向边方向弄反了——比如把 “u 依赖 v” 当成 u → v，其实该是 v → u。
