直接判断有无环就行，注意对邻接表初始化，不然就WA了
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; vector <int> e[maxn << 1]; int in[maxn], n, m, flag, X; void init() { memset(in, 0, sizeof(in)); for (int i = 0; i < n; i++) e[i].clear(); // 初始化 X = 0, flag = false; } void topsort() { queue <int> q; for (int i = 0; i < n; i++) { if (!in[i]) q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); X++; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; in[v]--; if (!in[v]) q.push(v); } } if (X == n) flag = true; // 无环则成立 } int main() { while (cin >> n >> m && n + m) { init(); for (int i = 0; i < m; i++) { int ui, vi; cin >> ui >> vi; e[ui].push_back(vi); in[vi]++; } topsort(); if (flag) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
