九度OJ 教程81 拓扑排序——确立比赛名次
[csharp]//九度OJ 教程81 拓扑排序之确立比赛名次
//有向图利用存储矩阵存储，另设一个标记数组flag[]表示已经被删除的节点。
#include <stdio.h>
#include<string.h>
#define MAXS 502
int main()
{ www.zzzyk.com
int n,m,i,j,k,mark[MAXS][MAXS]={0},flag[MAXS];
while(~scanf("%d %d",&n,&m))
{
memset(mark,0,MAXS*MAXS*sizeof(int));
memset(flag,1,MAXS*sizeof(int));//设置未访问标志。
while(m--)
{
scanf("%d %d",&i,&j);
if(mark[i][j])continue;//防止易做图的case给重复输入某个结果……
mark[i][j]=1;
mark[0][j]++;//0行j列存储入度数，即选手j被击败的次数。
}
for(j=1;j<n;j++)//纯粹为了执行n-1次，没其他意思。取出前n-1名，最后一名单独处理，要加\n的。
{
for(k=1;k<=n;k++)
{
if(flag[k]&&(mark[0][k]==0))
{
flag[k]=0;//设置移除标志
break;//结束循环。
}
}
printf("%d ",k);
for(i=1;i<=n;i++)//把该点从图中去除。
{
if(mark[k][i])
{
mark[k][i]=0;
mark[0][i]--;//被击败数减一。
}
}
}
for(k=1;k<=n;k++)
{
if(flag[k]&&(mark[0][k]==0))
{
flag[k]=0;
break;
}
}
printf("%d\n",k);
}
return 0;
}
补充：软件开发 , C++ ,
