九度OJ 教程81 拓扑排序——确立比赛名次

九度题目地址：http://ac.jobdu.com/problem.php?cid=1040&pid=80

免费题目地址：http://acmclub.com/problem.php?id=1077

//九度OJ 教程81 拓扑排序之确立比赛名次//http://ac.jobdu.com/problem.php?cid=1040&pid=80//有向图利用存储矩阵存储，另设一个标记数组flag[]表示已经被删除的节点。#include <stdio.h>#include<string.h>#define MAXS 502int main(){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;}