拓扑排序

就系按图中节点度的个数来排序，入度少优先

存图时用数组统计每个节点的入度，用队列/数组模拟，入度为0的先入队，遍历相邻节点，入度--，入度为0的再入队，同时存点，直至队列为空

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int INF=0x3f3f3f3f;typedef pair
              
                p;typedef long long ll;#define fi first#define se second#define MAXN 100000+5#define NIL -1#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))struct node{ int next, to; //edge[i].to 存 第i条边 的终点 .next存与边i同起点的前一条边}edge[MAXN];int head[MAXN]; //head[i] i为有边节点 head存该节点 边 的最大编号 存的是边int cnt;int indegree[MAXN];void add(int u, int v){ edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++;}int main(){ int i, j, k, l; int n, m; int u, v; while(cin>>n>>m && (n||m)) //n节点个数 m边数 一个节点可能有多条边 { cnt=0; me(head); mem(indegree); for(i=0; i
               
                >u>>v, indegree[v]++, add(u, v); int que[MAXN];//存节点 int iq=0; for(i=1; i<=n; i++) if(!indegree[i]) que[iq++]=i; //int x[MAXN]; j=0; for(i=0; i
                
                 =0; k--) { indegree[edge[k].to]--;//顺序输出的话 这三行k改为x[k] if(!indegree[edge[k].to]) que[iq++]=edge[k].to; } if(iq
                
               
              
             
            
           
          
         
        
       
      
     

一般拓扑排序都按字典序最小输出，这里要求数字最小先输出

先反向建图，改用优先队列，最后逆序输出就好了

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             

, cmp> q; for(i=1; i<=n; i++) if(!dep[i]) q.push(i); int b[N], l=0; while(q.size()) { k=q.top(); b[l++]=k; q.pop(); for(i=head[k]; ~i; i=e[i].next) { if(dep[e[i].to]) dep[e[i].to]--; if(!dep[e[i].to]) q.push(e[i].to); } } for(i=l-1; i>=1; i--) printf("%d ", b[i]); printf("%d\n", b[i]); } return 0;}