NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 18 题

关于拓扑排序，下面说法正确的是（ ）。

这题考拓扑排序的核心性质。拿到题先想：拓扑排序只存在于有向无环图（DAG），且每一步必须选入度为0的点。因此第一个点必然是入度为0的点，而环、唯一性、前后顺序都是常见陷阱，直接排除干扰项。

学生最容易错在以为‘连通’就能拓扑排序，忽略了有环的情况；或者误以为拓扑序唯一，其实只要入度为0的点不止一个，顺序就可以换；还有人会把‘入度为0的点一定排在前面’理解成‘所有入度为0的点都比所有入度大于0的点早’，这是错的，因为入度为0的点可能出现在序列中间甚至靠后位置，只要当时入度变0就行。

这道题考什么

拓扑排序的基础概念与性质，尤其是对DAG（有向无环图）的限制以及排序过程中入度为0的点的选取规则。

概念：人话讲拓扑排序

拓扑排序就是把有向图里的点排成一列，满足每条有向边都是从排在前面的点指向排在后面的点。但前提是图里不能有任何环——一旦有环，就永远找不到合法的排列顺序，所以拓扑排序只对DAG有意义。算法上，我们不断找当前入度为0的点（没前驱的点），把它放进结果序列，然后把它的出边删掉，被删边后新出现入度为0的点再选，直到所有点都被处理完。