拓扑排序必须在有向无环图（DAG）上进行，环存在则无解；C++标准库无内置实现，需手写DFS并用三态标记（0未访、1访问中、2已完成）检测环，逆后序入栈得结果。
拓扑排序的核心前提：必须是有向无环图（DAG）
如果图中存在环，topological sort 不存在——C++ 标准库不提供内置拓扑排序函数，必须手写。直接调用 std::sort 或基于比较的排序完全无效，因为边关系不是全序。先做环检测是必要步骤，否则结果不可靠。
用 DFS 实现拓扑排序（递归 + 状态标记）
常见错误是只用一个 visited 数组，导致无法区分「当前路径正在访问」和「已彻底处理完毕」。必须用三种状态：
-
0：未访问 -
1：正在当前 DFS 路径中（若再次遇到，说明有环） -
2：已访问完成（可安全加入结果）
逆后序（即 DFS 退出时压入栈）即为合法拓扑序。
#include <vector>
#include <stack>
using namespace std;
vector<int> topoSortDFS(const vector<vector<int>>& graph) {
int n = graph.size();
vector<int> state(n, 0); // 0=unvisited, 1=visiting, 2=done
stack<int> result;
bool hasCycle = false;
function<void(int)> dfs = [&](int u) {
if (state[u] == 1) { hasCycle = true; return; }
if (state[u] == 2) return;
state[u] = 1;
for (int v : graph[u]) {
dfs(v);
if (hasCycle) return;
}
state[u] = 2;
result.push(u);
};
for (int i = 0; i < n; ++i) {
if (state[i] == 0) dfs(i);
if (hasCycle) return {}; // 返回空表示失败
}
vector<int> ans;
while (!result.empty()) {
ans.push_back(result.top());
result.pop();
}
return ans;
}
用 BFS 实现拓扑排序（Kahn 算法）
更符合直觉：不断移除入度为 0 的节点，并更新邻居入度。关键点在于：
立即学习“C++免费学习笔记（深入）”；
- 必须预先计算每个节点的
indegree - 队列初始只含
indegree == 0的节点 - 最终结果长度 ≠ 图节点数 → 存在环
相比 DFS，Kahn 更易调试、天然支持多解（队列可用 std::queue 或 std::priority_queue 控制输出顺序），但需额外存储入度数组和队列。
#include <vector>
#include <queue>
using namespace std;
vector<int> topoSortKahn(const vector<vector<int>>& graph) {
int n = graph.size();
vector<int> indegree(n, 0);
for (int u = 0; u < n; ++u) {
for (int v : graph[u]) {
indegree[v]++;
}
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) q.push(i);
}
vector<int> ans;
while (!q.empty()) {
int u = q.front(); q.pop();
ans.push_back(u);
for (int v : graph[u]) {
indegree[v]--;
if (indegree[v] == 0) q.push(v);
}
}
return ans.size() == n ? ans : vector<int>{}; // 有环则返回空
}
实际使用时最容易忽略的细节
图的节点编号是否从 0 连续？若输入是字符串或稀疏 ID（如 "A", "task-3"），不能直接用 vector<vector>></vector>。得先做离散化映射：unordered_map<string int></string>。另外，边方向极易弄反——拓扑序要求「u → v」意味着 u 必须排在 v 前面，所以邻接表 graph[u] 应存的是 u 指向的节点，不是被指向的节点。
性能上，两种方法都是 O(V + E)，但 Kahn 的常数略大（需两次遍历建入度）；DFS 更省内存（无队列），但递归深度可能爆栈（对万级节点需手动改栈或转迭代 DFS）。
