拓扑排序问题(判断有向图是否有环）——C++实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN=500;
vector<int> graph[MAXN];//以邻接表（向量形式）组成的图
int inDegree[MAXN];//每个点的入度
bool TopologicalSort(int n){    //拓扑排序过程
   queue<int> node;//存入度为0的点
   for(int i=0;i<n;i++){
    if(inDegree[i]==0){
        node.push(i);
    }
   }
   int number=0;
   while(!node.empty()){  
    int u=node.front();
    node.pop();
    number++;
    for(int i=0;i<graph[u].size();i++){
        int v=graph[u][i];//获取与节点邻接的边
        inDegree[v]--;
        if(inDegree[v]==0){//若入度为0，则存入队列
            node.push(v);
        }
    }
   }
   return n==number;//若最后还有入度不为0的点，则说明图有环(若二者相等则无环）
}
int main(){
   int n,m;//n是节点数，m是边数
   while(scanf("%d%d",&n,&m)!=EOF){
    if(n==0){
        break;
    }
    memset(graph,0,sizeof(graph));//初始化图
    memset(inDegree,0,sizeof(inDegree));//初始化各点入度
    while(m--){
        int from,to;//边的起点和终点
        scanf("%d%d",&from,&to);
        graph[from].push_back(to);
        inDegree[to]++;
    }
    if(TopologicalSort(n)){
        printf("YES\n");
    } else{
        printf("NO\n");
    }
   }
   return 0;
}