拓扑排序

给定一个有向无环图(DAG)，排出所有顶点的一个序列A满足：对于图中每条有向边(x,y),x在A中都出现在y之前，则A是该图中的顶点的一个拓扑序

拓扑排序可以判断 有向图中是否有环 ，可以生成拓扑序列

Kahn（卡恩）算法

• e[x]存点x的邻点，res存拓扑序列，d[x]存x的入度

算法流程：核心用队列维护一个入度为0的节点的集合。

1. 初始化，队列q压入所有入度为0的点；
2. 每次从q中取出一个点x放入数组res;
3. 然后将×的所有出边删除。若将边(x,y)删除后，y的入度变为0，则将y压入q中
4. 不断重复2,3过程，直到队列q为空。
5. res中的元素个数等于n,则有拓扑序；否则，有环。