题解：AT_past202107_j 終わりなき旅

拓扑排序判环 适用场景：需要输出拓扑序或判断有向无环图。 时间复杂度：O(V+E)

#include<bits/stdc++.h> using namespace std; const int N = ; //自己定义 vector G[N]; int n, m, du[N]; bool check(int n) { queue q; int cnt = 0; //记录拓扑序的节点数 for (int i = 1; i <= n; i++) for (int v : G[i]) du[v]++; //初始化入度 for (int i = 1; i <= n; i++) if (du[i] == 0) q.push(i); //入度为0的节点入队 //BFS拓扑排序 while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (int v : G[u]) { du[v]--; if (du[v] == 0) q.push(v); } } return cnt != n; //若拓扑序节点数不足n，说明有环 } int main() { cin >> n >> m; while (m--) { int u, v; cin >> u >> v; G[u].push_back(v); } cout << (check(n) ? "有环" : "无环"); return 0; }