http://acm.hdu.edu.cn/showproblem.php?pid=1285
4 3 1 2 2 3 4 3
1 2 4 3
#include<stdio.h> #include<iostream> using namespace std; int map[505][505],pre[505]; int c[505]; int n,m; void topsort() { int i,j,k,p=1; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(pre[j]==0) // 如果该顶点入度为0 { pre[j]--; //删除该顶点,即该顶点入度减一 c[p++]=j; //删除元素储存到c[]数组中 for(k=1;k<=n;k++) { if(map[j][k]==1) //判断该顶点j与哪些点相连 pre[k]--; //若相连,则删除该边,即把与顶点j相连那点的入度减一 } break; } } } } int main () { int a,b,i; while(~scanf("%d%d",&n,&m)) { memset(pre,0,sizeof(pre)); memset(map,0,sizeof(map)); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); if(map[a][b]==0) // 要考虑重边情况 { map[a][b]=1; pre[b]++; } } topsort(); for(i=1;i<=n;i++) { if(i!=n) printf("%d ",c[i]); else printf("%d\n",c[i]); } } return 0; }
杭电 1285 确定比赛名次(拓扑排序),布布扣,bubuko.com
原文:http://blog.csdn.net/u012766950/article/details/38413519