拓撲排序,但題目要求按序號排出,按普通的拓撲排序不行,所以就每次從前往後搜
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int map[505][505]; int ans[505],du[505]; int n,i,j; void toposort() { for(i = 1 ; i <= n ; i ++) for(j = 1 ; j <= n ; j ++) if(map[i][j]) du[j] ++;//入度加1 int num = 1; while(num <= n) { i = 1; while(du[i]) i++;//找到入度為0的點 ans[num++] = i; du[i] = -1; for(j = 1 ; j <= n ; j ++) if(map[i][j]) du[j]--;//將所有與節點i相連的節點的入度值全部減1 } } int main() { int m; while(~scanf("%d%d",&n,&m)) { memset(map,0,sizeof(map)); memset(du,0,sizeof(du)); while(m--) { scanf("%d%d",&i,&j); map[i][j] = 1; } toposort(); for(i = 1 ; i < n; i ++) printf("%d ",ans[i]); printf("%d\n",ans[n]); } return 0; }