DFS拓扑排序同步环检测：用三色标记（0/1/2）区分未访问、递归中、已完成状态，遇灰色节点即环；Kahn算法通过统计输出节点数是否等于总节点数判环。
用 DFS 实现拓扑排序并同步检测环
DFS 是最直观的方案：一边递归遍历，一边用三种状态标记节点（未访问 / 正在访问 / 已完成），只要在「正在访问」状态下再次碰到同一节点，就说明存在环。visited 数组存状态（比如 0 未访问、1 正在访问、2 已完成），递归返回前把当前节点标为 2。
常见错误是只用 bool 类型的 visited，这样无法区分「已回溯完成」和「当前路径中」，导致误判环。也有人忘记在进入递归前设为 1，或忘记在递归后恢复状态（其实不需要恢复，但必须设为 2 表示已处理完毕）。
示例关键逻辑：
vector<int> state(n, 0); // 0: unvisited, 1: visiting, 2: visited
function<bool(int)> dfs = [&](int u) -> bool {
if (state[u] == 1) return false; // cycle detected
if (state[u] == 2) return true; // already processed
state[u] = 1;
for (int v : graph[u]) {
if (!dfs(v)) return false;
}
state[u] = 2;
result.push_back(u); // reverse order
return true;
};
用 Kahn 算法做拓扑排序时判断是否成环
Kahn 算法本质是不断剥离入度为 0 的节点。如果最终加入结果的节点数少于图中总节点数，说明剩下节点构成环（因为它们入度永远不为 0）。
立即学习“C++免费学习笔记（深入）”；
注意点：indeg 数组必须初始化正确；队列初始应加入所有 indeg[i] == 0 的节点；每次从队列弹出节点后，要遍历其所有邻接点并更新 indeg[v]--，仅当 indeg[v] == 0 才入队。
性能上，Kahn 是标准 BFS，时间 O(V + E)，空间 O(V + E)，比 DFS 更易调试；但它不记录环的具体路径，只回答「有没有环」。
关键判断代码段：
queue<int> q;
for (int i = 0; i < n; ++i)
if (indeg[i] == 0) q.push(i);
vector<int> topo;
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (int v : graph[u]) {
if (--indeg[v] == 0) q.push(v);
}
}
if (topo.size() != n) return false; // has cycle
邻接表 vs 邻接矩阵对实现的影响
实际写的时候几乎都用邻接表（vector<vector<int>> graph），因为稀疏图更常见，且遍历邻居效率高。若用邻接矩阵（vector<vector<bool>> mat），DFS 中找邻居就得遍历整行，时间退化到 O(V²)；Kahn 中更新入度也要扫整列，同样低效。
另外，输入如果是边列表（如 vector<pair<int,int>> edges），别忘了先建图并统计入度——漏掉某条边会导致 indeg 错误，进而让 Kahn 误判无环。
小提醒：graph[u] 存的是 u 指向的节点，不是反向；Kahn 依赖的入度必须是「指向 u 的边数」，方向弄反是新手高频 bug。
有重边或自环时怎么处理
自环（u → u）直接构成长度为 1 的环，DFS 在 state[u] == 1 时立刻捕获；Kahn 中它会让 indeg[u] 至少为 1，且无法被消到 0，最终导致 topo.size() < n。
重边（多条 u → v）本身不影响环判定，但会干扰入度统计：如果建图时没去重，indeg[v] 会被重复加，后续减操作也会多减，可能提前变成 0 或负数。所以要么建图时用 set 去重，要么确保输入边唯一——否则 Kahn 可能漏判环。
实践中建议预处理边集：set<pair<int,int>> edgeSet，再转邻接表，避免隐性逻辑错误。
真正容易被忽略的是：两种方法对「空图」「单点无边」「多个连通分量」都天然兼容，但如果你手动写了循环起点（比如只从节点 0 开始 DFS），就会漏掉其他连通块里的环。务必确保遍历全部节点。
