理解拓扑排序，首先要大致了解一下拓扑序列，设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，那么这个序列当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。拓扑排序就是对一个有向图构造拓扑序列的过程。
1.从有向图中选择一个没有前驱(度为0)的顶点输出。 2.从有向图中删去该顶点，并删去以该顶点为尾的弧。 3.重复上述两步，直至全部输出，或最后剩下若干的环。 思路很简单，详细过程代码中注释。美中不足，编译的时间有点长…
#include <bits/stdc++.h> using namespace std; #define N 100 int mp[N][N]; int n,l,a,b; void solve() { int k,sum=0,vis[N]={0},ss; while(1) { ss=0; for(int i=1;i<=n;i++) { k=0; for(int j=1;j<=n;j++) { if(mp[j][i]==1)//计算入度 { k++; } } if(k==0) { if(vis[i]==0)//用来标记删除的顶点 { cout<<i<<" "; ss=1; //ss用来判断是否输出完毕 vis[i]=1; sum++; } for(int h=1;h<=n;h++) { mp[i][h]=0; //删去以该顶点为尾的弧 } } } if(ss==0) { cout<<endl; if(sum==n) //sum用来计算输出顶点数量，全部输出则不存在环 { cout<<"改图中不存在环"; } else { cout<<"该图中存在环"; } break; } } } int main() { for(int i=1;i<=N-1;i++)//初始化 { for(int j=1;j<=N-1;j++) { mp[i][j]=0; } } cin>>n>>l; for(int i = 1; i <= l; i++) { cin>>a>>b; mp[a][b]=1;//存在弧为1 } solve(); return 0; }