首先来理解什么是拓扑排序；拓扑排序简单说是做事情的先后顺序，在现实生活中,人们经常要做连串事情，这些事情之闻有顺序关系或者依赖关系，在做一件事情之前必须先做另一件事，比如安排客人的座位、穿衣服的先后、课程学习的先后等。这些事情都可以抽象为图论中的拓扑排序。
拓扑排序的概念：
设有a、b、c、d等事情,其中a有最高优先级,b、c优先级相同,d是最低优先级，表示为a→(b,c)→d,那么abcd或acbd都是可行的排序。把事情看成图的点，把先后关系看成有向边，问题转化为在图中求一个有先后关系的排序这就是拓扑排序，显然，一个图能进行拓扑排序的完要条件是它是一个有向无环图(DAG)。有环图不能进行拓扑排序，
当然，这里还要普及两个图的简单概念：
出度：从一个点为起点的出去的边的数量为出度；
入度：以一个点为终点出去的边的数量为出度。
从入度和长度的概念上可以看出，如果一个点的入度数量为0，那这个点必定是最前面的点，如果出度等于0，则这个点必定又是最后面的点；
同时，拓扑排序是基于bfs和dfs的思想实现的，我们就来普及一下对于bfs与dfs拓扑排序的实现方式；
1.bfs：
bfs拓扑排序是常用的拓扑排序算法，这个算法是基于队列来实现的
而实现的思想，则是基于无前驱的顶点优先和无后继的顶点优先
1.无前驱的顶点优先：
以此图为例，
实现的步骤主要是：
（1）先找图中入度为0的点，作为起点放进队列，当然，这些点的先后顺序是无所谓的，主要是得有，如果找完一圈都没有发现图纸有度为0的点，那这个图就不是DAG图，不存在拓扑排序；
（2）在找完图中入度为0的节点之后，我们弹出队首元素，并且将队首元素的邻居的度都减一，把度减为0的邻居放进队列
（3）重复以上步骤，直到队列为空；
拿上图来说，会输出acbd，这就是上图的拓扑序列；
当然，如果队列空了，但是依旧是还有别的点没有进入队列，那这个图就不DAG，也就不存在脱坡序列；
2.无后继顶点优先：
将无前驱节点优先的执行反过来就是无后继顶点优先的执行。
2.基于dfs的拓扑排序
dfs是天然的拓扑排序思想的体现，dfs的原理就是一条路走到黑，一直搜素到最后，然后逐层回退，正是点与点的先后关系。
一个DAG，如果只有一个点是0入度的，从这个点开始拓扑排序，返回的顺序是逆序的拓扑排序，
因为递归返回的是最后的点，这里就没有后继点了，逐层回退，最后到起点
为了得到正序的拓扑序列，数据结构中有一个专门对付逆序的线性结构---那就是栈，用栈记录拓扑序列在输出就可以得到正确的拓扑序列；
但是依旧是有一些细节问题：
(1)应该以入度为0的点为起点开始DFS.如何找到它?需要找到它吗?如果有多个入度为0的点呢?
这几个问题其实并不用特别处理。想象有一个虚拟的点 v,，它单向连接到所有其他点。这个点就是图中唯一 的0入度点，图中所有其他的点都是它的下一层递归，而且它不会把原图变成环路。从这个虚拟点开始DFS就完成了拓扑排序。但运算的时候并不需要处理这个虚拟点，只要在主程序中把每个点轮流执行一 DFS可这样做相当于显式地道归了虚点的所有下一层点，
(2)如果图不是DAG,能判断吗?
图不是DAG，说明图是有环图，不存在拓扑排序。(那么在递归的时候会出现回退边)
在程序中这样发现回退边:记录每个点的状态,如果dfs递归到某个点时发现它仍在前面的递归中没有处理完毕，说明存在回退边，不存在拓扑排序:
还要一些杂项问题：
输出字典序最小的拓扑排序；
这种题目比如杭电1285和北大1270都有体现；
解决这里问题，核心是在当前步骤，在所有入度为0的点中输出编号最小的，
这里我们不用next_permutation();
这里采用的是优先队列：
在bfs拓扑排序中，把普通队列改为优先队列，放进入度为0的节点，每次输出最小编号........就是重复bfs拓扑排序的步骤啦
题目实战：https://www.dotcpp.com/oj/problem1707.html
这道题前面我已发博客：https://www.cnblogs.com/LQS-blog/p/16207985.html
来个重量级的:
https://www.acwing.com/problem/content/description/166/
友情提示，这道题不太好做，慎入；
这里只给出代码，今天很晚了，以后找时间专门出篇博客：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int num=30010; 4 queue<int>q; 5 int n,m; 6 vector<int>edge[num];//存图 7 vector<int>topo;//拓扑序列 8 int in[num];//入度数组 9 bitset<num>f[num];//是标准库中的一个固定大小序列，其储存的数据只包含 0/1 10 int main() 11 { 12 std::ios::sync_with_stdio(false); 13 cin>>n>>m; 14 for(register int i=0;i<m;i++)//常规存图入度操作 15 { 16 int a,b; 17 cin>>a>>b; 18 edge[a].push_back(b); 19 in[b]++; 20 } 21 for(register int i=0;i<n;i++)//把入度为0的点入队 22 { 23 if(!in[i]) 24 q.push(i); 25 } 26 while(!q.empty()) 27 { 28 int x=q.front();//取队首 29 q.pop(); 30 topo.push_back(x);//存入拓扑序列 31 for(register int j=0;j<edge[x].size();j++)//找邻居 32 { 33 int y=edge[x][j]; 34 in[y]--;//度减1 35 if(!in[y])//找邻居度为0的节点 36 q.push(y); 37 } 38 } 39 for(register int i=topo.size()-1;i>=0;i--) 40 { 41 int x=topo[i]; 42 f[x].reset();//置所以位为0 43 f[x][x]=1; // x这个点可以到达自己 f[x][x] =表示从 x出发的点， 44 for(register int k=0;k<edge[x].size();k++) 45 { 46 f[x]|=f[edge[x][k]];//x这个点可以到达的点的数量= {x} U {y1} U {y2}..{yn} 47 } 48 } 49 for(register int i=1;i<=n;i++) 50 cout<<f[i].count()<<endl;// f[i].count() 返回f[i] 中 1的个数 51 return 0; 52 }