本文共 389 字，大约阅读时间需要 1 分钟。

拓扑排序用于AOV网络，结果不唯一。

步骤为：

找到一个入度为0的点，输出， 删除该点及其边 找下一个入度为0的点。

若执行完毕后，存在未输出的点，则此图是有环图。

实现上：

维护一个数据，记录每个点的入度。

维护一个栈，把找到的入度为0的点压入。 维护一个邻接表，记录出边。

例题：

窗口绘制： POJ2585

显示器由44个格子组成，显示器显示9个窗口，编号1～9，位置固定，左上角为1号，向左移1列为2号，依次类推，右下角为9号，每个窗口由22组成，窗口可以覆盖，给定一个显示器临时状态，问是窗口覆盖是否合理。

解法，构造AOV图。

1233

4566 7899 7899

1的区域有1，2，4，5，则1->2,1->4,1->5

2的区域有2，3，5，6，则2->3,2->5,2->6 3的区域有3，6，则3->6 依次类推，构造AOV图。 只需要判断存不存在环即可。

转载地址：http://ydwji.baihongyu.com/