Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 9840 Accepted
Submission(s): 3837
1 //46MS 1228K 758 B C++ 2 //最简单的拓扑排序 3 //O(n^2) 4 #include<stdio.h> 5 #include<string.h> 6 int g[505][505]; 7 int in[505],ans[505],n,m; 8 void topo() 9 { 10 for(int i=1;i<=n;i++) 11 for(int j=1;j<=n;j++) 12 if(g[i][j]) in[j]++; //in[]数组记录改点的入度 13 for(int i=1;i<=n;i++){ 14 int j=1; 15 while(in[j]!=0) j++; 16 ans[i]=j; //保存答案 17 in[j]--; //更新已取的点的入度 18 for(int k=1;k<=n;k++) 19 if(g[j][k]) in[k]--; //更新和节点j相连的点的入度 20 } 21 } 22 int main(void) 23 { 24 int a,b; 25 while(scanf("%d%d",&n,&m)!=EOF) 26 { 27 memset(g,0,sizeof(g)); 28 memset(in,0,sizeof(in)); 29 for(int i=0;i<m;i++){ 30 scanf("%d%d",&a,&b); 31 g[a][b]=1; 32 } 33 topo(); 34 for(int i=1;i<n;i++) 35 printf("%d ",ans[i]); 36 printf("%d\n",ans[n]); 37 } 38 return 0; 39 }
hdu 1285 确定比赛名次 (拓扑),布布扣,bubuko.com
原文:http://www.cnblogs.com/GO-NO-1/p/3622117.html