拓扑排序

拓扑排序是面试常考的题之一，O(m+n)的复杂度，m为边数，n为顶点数
解法：BFS,DFS两种解法。
用途：解决DAG图的问题，例如最长路，求满足DAG图关系的极值点。
DAG图：DAG意思是有向无环图，所谓有向无环图是指任意一条边有方向，且不存在环路的图。

bfs方法比较好写，暂时先用这个：DAG图无环那必然有始有终，起点的入度为0，终点的出度为0，可以通过这个性质使用队列来解题，每次push入 入度为0的点，然后删边，删入度，然后继续push。

207,210,269,329,444,851 leetcode的题

207课程表

这题就是判断图是不是一个DAG图
code：

207 solution
做法就是通过vector f保存入度，pp保存图，队列来进行bfs。
210同理，返回拓扑排序的结果

code：

210 sol
269 付费题，待补
329
329
这道题用dfs做应该也是可以的，但要非递归的做法，就要用到拓扑排序了。
建图：可以根据根据4个方向，按照递增的形式进行建图，建图的话，把二维数组可以用一维数组来表示。但跑的比递归还慢，先放code等会再优化。
图片.png
图片.png
444 付费题，待补
851

这道题题意比较乱，可以根据钱的数量进行拓扑排序，其中建图的顺序要注意，是满足x的钱大于y的钱条件进行连边，即x连向y，在拓扑排序中，使用一个数组进行转移最小的安静值。

851code

总结一下，bfs的写法比较固定，基本步骤
1.建图
2.压入队列

3. 拓扑排序
   一般题目给出相对顺序的时候，或者可以通过图间接求出相对顺序的时候，可以考虑使用拓扑排序，复杂度主要在建图的时候，bfs写法可以判断是否是DAG图，上面code默认为DAG图了，所以没有判断。
   难点:1.考虑连边的方向 2.其他状态的转移，例如329中的长度，851中的最小安静值

接下来，看一下DFS的写法，dfs还是写的不太熟练。
210题来个模板吧，写好的内容又丢了，抄个别人的模板把
https://www.cnblogs.com/fzl194/p/8747713.html

模板
dfs这种写法就比较难理解，待补