题解 | 课程表II

题干分析：

题设给予我们课程数量，且给予我们直接有前置关系的所有课程组，要求我们返回能够符合先学完前置课程后再学习后置课程的课程学习顺序，如果不存在（即有部分学科存在循环关联），则返回空数组。

算法思路：

本题个人解法是直接模拟拓扑排序的流程：遍历所有节点，找到入度为0的节点插入结果数组，然后去除从这些节点引出的所有指向其他节点的边。持续进行，直到找不到入度为0的节点。同时如果结果数组大小不等于课程数目，证明这些课程中有循环依赖课程组，需返回空数组。

实现代码：

vector<int> findOrder(int numCourses, vector<vector<int> > &prerequisites) {
        vector links(numCourses, 0); // 入度计数
        vector adj(numCourses, vector(numCourses, false)); // 邻接矩阵

        for (auto &link : prerequisites) { // 构建
            adj[link[1]][link[0]] = true; // 注意不要弄反了（踩坑过）
            links[link[0]]++;
            
        }

        vector<int> ans;
        auto check = [&]() -> int { // 找到入度为0的节点下标，找不到返回课程数
            for (int i = numCourses - 1; i >= 0; --i) { // 从尾部开始（也可以从头开始，单纯因为题目标准答案好像就是按照尾部开始找得来的）
                if (links[i] == 0) return i;
            }
            return numCourses;
        };
        for (int idx = check(); idx != numCourses; idx = check()) { // 拓扑排序
            ans.push_back(idx);
            links[idx] = -1;
            for (int i = 0; i < numCourses; ++i) {
                if (adj[idx][i]) {
                    adj[idx][i] = false;
                    links[i]--;
                }
            }
        }
        if (ans.size() < numCourses) return {};
        return ans;
    }

复杂度分析：

• 时间复杂度：最差情况下每个节点都相互依赖，循环执行n次，每次寻找入度为0节点为O（n），总计O（n^2）
• 空间复杂度：邻接矩阵O(n^2)占空间开销主体，空间复杂度总计O（n^2）