题目链接：
题目大意：有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。
解题思路：拓扑排序裸题，但是有要求并列的点序号小的排在前面。开始写了一个dfs版倒序的怎么写都错，后来发现根本做不了（可能是我太菜了）。。。。于是改写了一个通过每次查找入读为0的点，然后删除有关边的版本，一下就AC了。
先是对了的方法，先叫它减入度法吧，这种做法可以判断有向图是否成单链，也就是没有分支，若一次找到入度为0的点有两个则存在分支。
代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=5e2+5; 7 8 int n,m; 9 int degree[N];10 bool G[N][N];11 queue q;12 13 void toposort(){14 for(int i=1;i<=n;i++){15 //寻找入度为0的点16 int j=1;17 while(degree[j]!=0) j++;18 degree[j]--;19 q.push(j);20 //将关联的点的入度减1,即删除与该节点关联的边21 for(int k=1;k<=n;k++){22 if(G[j][k])23 degree[k]--;24 }25 }26 }27 28 int main(){29 while(~scanf("%d%d",&n,&m)){30 memset(G,false,sizeof(G));31 memset(degree,0,sizeof(degree));32 for(int i=1;i<=m;i++){33 int a,b;34 scanf("%d%d",&a,&b);35 if(!G[a][b]){36 G[a][b]=true;37 degree[b]++;38 } 39 }40 toposort();41 while(!q.empty()){42 if(q.size()==1)43 printf("%d\n",q.front());44 else45 printf("%d ",q.front());46 q.pop();47 }48 }49 return 0;50 }
然后是dfs版的，虽然不能写这题，但还是当个模板放着吧，dfs法可以在O（n^2）时间内判断是否有环，而floyd需要O（n^3）。
代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=5e2+5; 7 8 int n,m; 9 int G[N][N],vis[N];//vis[i]=0,-1,1分别表示未访问、正在访问、已访问并且已递归访问完所有子孙10 stack res;11 12 13 bool dfs(int u){14 vis[u]=-1;15 for(int i=1;i<=n;i++){16 if(G[u][i]){17 if(vis[i]<0) return false;18 else if(!vis[i]&&!dfs(i))19 return false;20 }21 }22 vis[u]=1;23 res.push(u);24 return true;25 }26 27 bool toposort(){28 memset(vis,0,sizeof(vis));29 for(int i=1;i<=n;i++){30 if(!vis[i]){31 if(!dfs(i)) return false;32 }33 }34 return true;35 }36 37 int main(){38 while(~scanf("%d%d",&n,&m)){39 memset(G,0,sizeof(G));40 for(int i=1;i<=m;i++){41 int a,b;42 scanf("%d%d",&a,&b);43 G[a][b]=1;44 }45 toposort();46 while(!res.empty()){47 if(res.size()==1)48 printf("%d\n",res.top());49 else50 printf("%d ",res.top());51 res.pop();52 }53 }54 return 0;55 }