拓扑序，解决具有层级性的问题。
A topological sort is an ordering of the nodes of a directed graph such that if there is a path from node a to node b, then node a appears before node b in the ordering. For example, for the graph one topological sort is [4,1,5,2,3,6]:
An acyclic(无环的) graph always has a topological sort. However, if the graph contains a cycle, it is not possible to form a topological sort, because no node of the cycle can appear before the other nodes of the cycle in the ordering. It turns out that depth-first search can be used to both check if a directed graph contains a cycle and, if it does not contain a cycle, to construct a topological sort.
- topsort就是有向图的宽度优先遍历的应用
- 拓扑序，不唯一
- 如要要字典序最小的拓扑序，在遍历入度为0的点的时候，从1开始遍历，并入队
- 有明显【层级关系】的问题，可以考虑用topsort()模型
例题，1964：【13NOIP普及组】车站分级
给出了m趟列车的停靠情况每一个车站有一个级别停靠的规则是，一旦停靠站A，那么后续经过的所有站，只要站的级别比A大，就要停靠问，这n个车站，满足m趟停靠规则的前提下，最少需要区分出来几个级别问题具有层级性
若有收获，就点个赞吧
0 人点赞
