hdu 1285 确定比赛名次 拓扑排序
4 3 1 2 2 3 4 3
1 2 4 3
拓扑排序,每次把入度为0的点输出,并删除这个点。
代码:
1 #include <iostream> 2 #include <iostream> 3 #include <stdio.h> 4 using namespace std; 5 6 int map[505][505],indegree[505]; 7 8 void Topo(int n) 9 { 10 int ans,i,j,flag=0; 11 for(i=1;i<=n;i++) 12 { 13 for(j=1;j<=n;j++) 14 { 15 ans=n; 16 if(indegree[j]==0) 17 { 18 flag++; 19 indegree[j]--; 20 ans=j; 21 if(flag!=n) 22 printf("%d ",ans); 23 else 24 { 25 printf("%d\n",ans); 26 return ; 27 } 28 break; 29 } 30 } 31 for(j=1;j<=n;j++) 32 { 33 if(map[ans][j]>0) 34 { 35 indegree[j]--; 36 } 37 } 38 } 39 } 40 41 int main() 42 { 43 int i,j,n,m,flag; 44 while(scanf("%d%d",&n,&m)!=EOF) 45 { 46 int p,q; 47 memset(map,0,sizeof(map)); 48 memset(indegree,0,sizeof(indegree)); 49 for(i=0;i<m;i++) 50 { 51 scanf("%d%d",&p,&q); 52 if(map[p][q]==0) 53 { 54 map[p][q]=1; 55 indegree[q]++; 56 } 57 } 58 Topo(n); 59 } 60 return 0; 61 }优质内容筛选与推荐>>