拓扑排序仅适用于有向无环图（dag），其环检测能力源于bfs能否遍历全部节点：若结果序列长度等于节点总数则无环，否则存在环；实现时需正确初始化入度数组、建图方向、仅入度为0时入队，并包含孤立点。
拓扑排序前先确认图是有向无环图（DAG）
拓扑排序本身不检测环路，它只对 DAG 有效；一旦图中存在环，topological_sort 就无法排出全部节点——你得到的序列长度会小于节点总数。所以「检测环路」其实是拓扑排序过程的副产物：不是额外加一步判断，而是看 BFS 是否能遍历完所有节点。
用入度表 + BFS 实现时，关键在初始化和队列维护
核心逻辑是：统计每个节点的入度（indegree[v]），把所有 indegree[v] == 0 的节点入队，然后逐个取出、删边、更新邻居入度。容易出错的地方集中在：
-
indegree数组必须初始化为 0，否则未出现的节点可能含随机值 - 建图时若用
vector<vector>></vector>，注意索引从 0 开始还是 1 开始，别让graph[u].push_back(v)写反方向（应是 u → v，即 v 的入度要 +1） - 更新邻居入度后，**只有当新入度恰好为 0 才入队**，不能大于 0 也塞进去
- 如果图含孤立点（无边连入也无边连出），它的入度是 0，必须被初始入队，否则漏计数
判断是否有环只需比对结果序列长度与节点总数
执行完 BFS 后，拓扑序存于 result vector 中。此时：
- 若
result.size() == n（n是节点总数），说明无环，result就是合法拓扑序 - 若
result.size() ，说明存在至少一个环，无法完成排序
不需要额外 DFS 或标记环上节点——BFS 卡住的位置就是环的入口区域，但定位具体哪条边成环需回溯，那已超出拓扑排序职责范围。
C++ 示例代码（精简可运行版）
#include <vector>
#include <queue>
using namespace std;
vector<int> topo_sort(int n, const vector<vector>>& edges) {
vector<int> indegree(n, 0);
vector<vector>> graph(n);
for (auto& e : edges) {
int u = e[0], v = e[1]; // u -> v
graph[u].push_back(v);
indegree[v]++;
}
queue<int> q;
for (int i = 0; i result;
while (!q.empty()) {
int u = q.front(); q.pop();
result.push_back(u);
for (int v : graph[u]) {
indegree[v]--;
if (indegree[v] == 0) q.push(v);
}
}
return result; // 返回空 vector 也合法，调用方检查 size()
}
</int></vector></int></vector></int></queue></vector>
调用时注意：节点编号默认为 0 到 n-1；若输入是字母或字符串 ID，得先做离散化映射到整数索引。还有，edges 里每条边必须是有效的有向边，重复边会导致 indegree 被多加，从而掩盖真实环路——去重得靠外部保证。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
