我不是来水博客的
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int maxv=100,maxe=100; struct rec{ int x,y,next; }a[maxe+10]; int n,e; int ls[maxv+10],in[maxv+10],list[maxv+10]; void init() { scanf("%d%d",&n,&e); memset(ls,0,sizeof(ls)); for(int i=1;i<=e;i++){ scanf("%d%d",&a[i].x,&a[i].y); a[i].next=ls[a[i].x]; ls[a[i].x]=i; } } int l=0,r=0,q[maxv+10]; //l表示队首位置 r表示队尾位置 q为手动队列 void topsort(){ int cnt=0; memset(in,0,sizeof(in)); for(int i=1;i<=e;i++) in[a[i].y]++;//统计入度 for(int i=1;i<=n;i++) if(!in[i]) q[++r]=i;//将入度为0的点加入队列 //l<rcn表示队列中仍有点未遍历 即仍未拓扑完全 while(l<r){ l++; int x=q[l]; list[++cnt]=x; for(int i=ls[x];i;i=a[i].next){ int y=a[i].y; in[y]--; if(!in[y]) q[++r]=y;//在拓扑过程中入度为0的点也加入队列 } } } void print() { for(int i=1;i<=n;i++) printf("%d ",list[i]); } int main() { init(); topsort(); print(); }