http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=380#problem/A
这道题表面上简单,实际上也简单
#include<stdio.h>
#include<string.h>
#define MAX 500
int relative[MAX][MAX],indegree[MAX];
void topologicalsort(int n){
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(!indegree[j]){//找到并去掉入度为零的点
indegree[j]–;
if(i!=n)//控制输出格式
printf("%d ",j);
else
printf("%d\n",j);
for(k=1;k<=n;k++){//与j有关系的边去掉,点的入度减一
if(relative[j][k])
indegree[k]–;
}
break;
}
}
int main(){
int n,m,a,b,i;
while(scanf("%d%d",&n,&m)!=EOF){
memset(relative,0,sizeof(relative));
memset(indegree,0,sizeof(indegree));
for(i=0;i<m;i++){
scanf("%d%d",&a,&b);
if(!relative[a][b]){
relative[a][b]=1;
indegree[b]++;
}
}
topologicalsort(n);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation