有两种方法实现：
方法一：通过循环查找。
1、输入邻接矩阵并保存点与点之间的关系，用数组保存每个点的入度。
2、每次找一个入度为零的点，将所有和他有关的点的入度减一。
3、重复步骤二，直到没有入度为零的点为止。
#include<iostream> #include<cstring> #define MaxN 12 using namespace std; int mp[MaxN][MaxN]; int cont[MaxN]; int n,m; void TopSort() { int flag; for(int i=1; i<=n; i++) //需要查找n次 { flag=0; for(int j=1; j<=n; j++) { if(!cont[j]) { cout<<j<<" "; flag=1; cont[j]--; for(int k=1; k<=n; k++) if(mp[j][k]) cont[k]--; break; //每次只找一个入度为零的节点 } } if(!flag) //如果结点未输出完，图中就没有了入度为零的结点，证明有环，则不合法 break; } if(flag) cout<<"YES\n"; else cout<<"NO\n"; } int main() { while(cin>>n>>m) { memset(mp,0,sizeof(mp)); memset(cont,0,sizeof(cont)); int a,b; for(int i=0; i<m; i++) { cin>>a>>b; mp[a][b]=1; cont[b]++; } TopSort(); } return 0; } 方法二：借助栈实现。
1、将初始时所以入度为0的顶点依次入栈。
2、当入度为0的顶点不为空时，重复执行：
｛
1) 取栈顶顶点；
2)从AOV网络中删除该顶点以及它发出的每条边，边的终点入度减一；
3）如果入度为0，则该顶点入栈。
｝
3、如果输出顶点个数少于AOV网络中顶点个数，则有环。
#include<iostream> #include<stack> #include<cstring> #define MaxN 12 using namespace std; struct node { int d; node *next; }*lis[MaxN]; int count[MaxN]; int n,m; void TopSort() { stack<int >s; node *p; int sum=0; for(int i=1; i<=n; i++) { if(!count[i]) s.push(i); } while(!s.empty()) { int t=s.top(); s.pop(); sum++; //cout<<t<<" "; p=lis[t]; while(p) { count[p->d]--; if(!count[p->d]) s.push(p->d); p=p->next; } lis[t]==NULL; //注意，将节点删掉 } if(sum==n) cout<<"YES\n"; else cout<<"NO\n"; } int main() { while(cin>>n>>m) { for(int i=0; i<n; i++) lis[i]=NULL; memset(count,0,sizeof(count)); int a,b; for(int i=0; i<m; i++) { cin>>a>>b; count[b]++; node *p=new node; p->d=b; p->next=lis[a]; lis[a]=p; } TopSort(); } return 0; }
