引入

离散教材上讲过关键路径。其中，在求最长路径时，第一步是对节点进行“重新标号”。经过查阅，发现这个步骤其实叫做“拓扑排序”。很容易知道，如果一个图可以拓扑排序，那个它是有向无环图（DAG, Directed Acyclic Graph），从而它可能是一个能反映事件先后依赖关系的PT图（Potentialtask Graph）。

问题

(1) LeetCode #207

“能完成学习”说明给的图是DAG。用拓扑排序判断给定图是否是DAG图即可。即如果还有节点没有标号时，图中就找不到入度为0的点了，那么就不是DAG。反之，能顺利给所有点标号，就是DAG。

(2) LeetCode #210

本题其实就是在1的基础上，把拓扑排序的结果输出出来。

(3) LeetCode #1203

本题要求每个小组的工作排在一起。其实，这是一个双重（嵌套）拓扑排序的结构。可以先将每个组的工作“打包”构建整个小组之间的PT图（先后关系）进行拓扑排序，然后对每个组内的工作再进行拓扑排序。

实现

(1)

本题有两点实现上的技巧。

一开始实现的时候比较愚笨地把给的边列表转换成了邻接矩阵。但其实本题用邻接表（adjacency list）在空间和时间上都更优。因为，在删除一个点，需要知道它的直接后继时，用邻接表可以直接遍历这个点的后继列表，而邻接矩阵需要遍历所有的点并用if判断。同时，为了避免不断地盲目扫描全部节点来获取入度为0的点，应该借助一个队列。一开始，把所有入度为0的点加入队列。由于每个点的入度变化是每次删除一个点时可能减1，也就是新产生的入度为0的点一定是删除某个点时它的入度从1变成0，因此一边删除点，就可以一边把新的入度为0的点加入队列。队列空了之后，判断是否删除了所有点即可。

LeetCode的输入数据往往给的是边列表。从此题可以看出，边列表有时应转换成邻接矩阵，有时应转换成邻接表。（说不定有时也可以直接使用。）

class Solution
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<int> pre_num(numCourses, 0);
        vector< vector<int> > adjacency(numCourses);
        for (auto iter : prerequisites)
        {
            // iter[1] -> iter[0]
            pre_num[ iter[0] ]++;
            adjacency[ iter[1] ].push_back(iter[0]);
        }
        queue<int> q;
        for (int i = 0; i < numCourses; i++)
        {
            if (pre_num[i] == 0)
                q.push(i);
        }
        int n = numCourses;
        while (!q.empty())
        {
            int node_to_del = q.front();
            q.pop();
            n--;
            for (auto iter : adjacency[node_to_del])
            {
                pre_num[iter]--;
                if (pre_num[iter] == 0)
                    q.push(iter);
            }
        }
        return n == 0;
    }
};

(2)

对1略加改造即可。

class Solution
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<int> order;
        vector< vector<int> > adjacency(numCourses);
        vector<int> pre_num(numCourses, 0);
        for (auto iter : prerequisites)
        {
            // iter[1] -> iter[0]
            adjacency[ iter[1] ].push_back(iter[0]);
            pre_num[ iter[0] ]++;
        }
        queue<int> q;
        for (int i = 0; i < numCourses; i++)
        {
            if (pre_num[i] == 0)
                q.push(i);
        }
        while (!q.empty())
        {
            int node_to_del = -1;
            node_to_del = q.front();
            q.pop();
            order.push_back(node_to_del);
            for (auto iter : adjacency[node_to_del])
            {
                // node_to_del -> iter
                pre_num[iter]--;
                if (pre_num[iter] == 0)
                    q.push(iter);
            }
        }
        if (order.size() == numCourses)
            return order;
        else
            return vector<int>(0);
    }
};