题目描述

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，
比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁
判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1
赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；
其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M
行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小
的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符
合要求的排名。

C++

//#include<bits/stdc++.h>
/*
基于bfs的最小字典序的拓扑排序 

*/
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std ;

const int N = 510 ;
int n , m ;
int h[N] , ne[N] , e[N] , idx ; 
int in[N] , out[N] ; 
int ans[N] , cnt ;


void  add(int a ,int b ) 
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ; 
}

void bfs() 
{
    priority_queue<int ,vector<int>,greater<int>> q ;
    for(int i = 1 ; i <= n ; i ++ ) 
    {
        if(!in[i]) q.push(i) ; 
    }
    if(!q.size()) return ;  // 没有入度为0 的点，说明不是DAG 


    while(q.size())
    {
        auto t = q.top() ;
        q.pop() ;
        ans[cnt++] = t ; 

        for(int i= h[t] ; ~i ; i = ne[i]) 
        {
            int j = e[i] ;
            in[j] -- ;
            if(!in[j]) q.push(j) ; 
        }
    }
}

void init() 
{
    memset(h, -1 , sizeof h ) ; 
    memset(in, 0, sizeof in ) ; 
    memset(out, 0 , sizeof out ) ; 
    memset(ans,0,sizeof ans) ;
    cnt = 0 ;
    idx = 0 ;
}




int main()
{

    while(~scanf("%d%d", &n ,&m ))
    {

        init() ;
        for(int i = 0 ; i < m ; i ++ ) 
        {
            int a , b ;
            scanf("%d%d",&a,&b) ;
            add(a,b) ;
            in[b] ++ ;
            out[a] ++ ;
        }
        bfs() ;
        for(int i = 0 ; i < cnt ; i ++ ) 
        {
            if(i < cnt -1 )printf("%d ",ans[i]) ;
            else printf("%d",ans[i]) ;
        }
        puts("") ;
    }

    return 0 ;
}

总结：

求拓扑排序可以通过bfs和dfs实现。各有优势。
dfs天生适合对图进行拓扑排序，它的遍历天然符合拓扑排序的原理。但是缺点是没有办法按照字典序
最小进输出。因为dfs处理的是上下层的关系，不能处理层次之间的关系。

bfs求拓扑排序有无前驱顶点优先和无后继顶点优先。正常思路下，无前驱顶点优先就可以了。而且使用
优先队列可以保证输出的拓扑排序是字典序最小的那个答案。

综上所述，求拓扑排序，只需要记住`bfs输出字典序最小`的算法，基本没有问题。