使用队列。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int N = 501; int n, m; vector<int> graph[N]; int indegree[N]; bool func(int n){ queue<int> node; //存入度为0的点 for(int i = 0; i < n; i++){ if(indegree[i] == 0){ node.push(i); } } int num = 0; //拓扑序列顶点个数 while(!node.empty()){ int u = node.front(); node.pop(); num++; //拓扑序列顶点个数 +1 for(int i = 0; i < graph[u].size(); i++){ int v = graph[u][i]; indegree[v]--; //后续节点入度-1 if(indegree[v] == 0){ node.push(v); } } } return n == num; //是否产生拓扑排序 } int main(){ int from, to; while(cin >> n >> m){ if(n == 0 && m == 0) break; memset(graph, 0, sizeof(graph)); memset(indegree, 0, sizeof(indegree)); while(m--){ cin >> from >> to; graph[from].push_back(to); indegree[to]++; } if(func(n)){ printf("YES\n"); }else{ printf("NO\n"); } } return 0; }