1.如果有向图无回路,,那么该图拓扑有序。
2代码:
#include<cstdio>#include<cstring>using namespace std;int mat[505][505];int n,m;int in[505];void topological_sort(){int cnt=n;while(cnt–){int i;for(i=1; i<=n; i++){if(in[i]==0)break;}printf("%d",i);in[i]=-1;if(cnt){printf(" ");}for(int j=1; j<=n; j++){in[j]-=(mat[i][j]);}}printf("\n");}int main(){while(scanf("%d%d",&n,&m)==2){memset(mat,0,sizeof(mat));memset(in,0,sizeof(in));for(int i=0; i<m; i++){int a,b;scanf("%d%d",&a,&b);mat[a][b]++;in[b]++;}topological_sort();}return 0;}
版权声明:本文为博主原创文章,未经博主允许不得转载。
找一个让心里安静和干净的地方,