用来处理有事件(点)存在先后关系的算法。
经典应用：工程图
也可以处理已知序列之间大小关系，求一组可行解。
分析问题，抽象出点和边，建DAG图，方向是先开始的指向后开始，维护每个顶点的入度。
将入度为0的顶点放入队列中，BFS即可。BFS过程中，每遍历一次u->v，将这条边删去，即v入度减一，若v入度为0也放入队列中。
直到队列为空，算法结束。可以将队列中的不同点个数存起来，若等于n则存在拓扑序，否则该图不存在拓扑结构。DAG一定存在。
显然拓扑排序的时间复杂度为O(n+e)。
如果一个DAG有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点所需的时间是O(n)。
在正常情况下，每个顶点进一次栈，出一次栈，所需时间O(n)。每个顶点入度减1的运算共执行了e次。
所以总的时间复杂为O(n+e)。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef pair<int,int> piir; 4 typedef long long ll; 5 const int maxn = 1e2+5; 6 const int INF = 0x3f3f3f3f; 7 8 int n,m; 9 int in[maxn]; 10 vector<int> G[maxn],ans; 11 queue<int> q; 12 13 void top(){ 14 while(!q.empty()) q.pop(); 15 for(int i=1;i<=n;i++) 16 if(in[i]==0) q.push(i); 17 18 while(!q.empty()){ 19 int u=q.front();q.pop(); 20 ans.push_back(u); 21 for(auto v : G[u]){ 22 in[v]--; 23 if(in[v]==0) q.push(v); 24 } 25 } 26 } 27 void init(){ 28 memset(in,0,sizeof(in)); 29 ans.clear(); 30 for(int i=1;i<=n;i++) 31 G[i].clear(); 32 } 33 int main(){ 34 while(scanf("%d%d",&n,&m) && n+m){ 35 init(); 36 for(int u,v,i=1;i<=m;i++){ 37 scanf("%d%d",&u,&v); 38 G[u].push_back(v); 39 in[v]++; 40 } 41 top(); 42 43 for(auto it : ans) 44 printf("%d ",it); 45 printf("\n"); 46 } 47 return 0; 48 }
原文：https://www.cnblogs.com/ordinarv/p/11771459.html
