在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。

每个顶点出现且只出现一次；

若A在序列中排在B的前面，则在图中不存在从B到A的路径。

也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面[1]。

摘自

题意

拓扑排序模板题，输出时要求在满足条件的情况下小的编号在前

code（DFS实现，错误）

DFS有问题，无法保证小的编号在前。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN = 505;int n, m;int c[MAXN]; // 表示当前点的状态 -1:正在访问 1:已访问 0:未访问vector
         
           G[MAXN];int sta[MAXN], top;bool dfs(int u){ c[u] = -1; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(c[v] < 0) return false; // 存在环 if(!c[v] && !dfs(v)) return false; } c[u] = 1; sta[--top] = u; return true;}bool toposort(){ top = n; memset(c, 0, sizeof c); for(int i = 1; i <= n; i--) // 点 1...n if(!c[i] && !dfs(i)) return false; return true;}int main(){ while(~scanf("%d%d", &n, &m)) { for(int i = 0; i <= n; i++) G[i].clear(); for(int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); G[x].push_back(y); } toposort(); for(int i = 0; i < n; i++) printf("%d%c", sta[i], i == n - 1 ? '\n' : ' '); } return 0;}
         
        
       
      
     
    

code(优先队列实现)

#include 
    
     #include 
     
      #include 
      
       #include
       
        #include 
        
         #include 
         
          using namespace std;const int MAXN = 505;int n, m;int c[MAXN];vector
          
            G[MAXN];vector
           
             topolist;int toposort(){ priority_queue