拓扑排序-理解

用来处理有事件(点)存在先后关系的算法。

经典应用：工程图
也可以处理已知序列之间大小关系，求一组可行解。

算法流程

分析问题，抽象出点和边，建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 }

View Code