题解 | 课程表IV

题干分析：

题设给予我们课程个数，一个二维数组标识某门课程是另一门课程的直接前置课程，同时给予我们需要进行判定是否为前置课程（包括直接与间接前置）的课程组，要求我们返回这些课程组的判定结果。

算法思路：

通过题设给予的信息构建邻接矩阵，然后使用Warshall算法求出可达性矩阵。此后我们根据需要查询的课程对，在此可达性矩阵中直接查询结果即可。

实现代码：

vector<bool> checkIfPrerequisite(
        int numCourses,
        vector<vector<int> > &prerequisites,
        vector<vector<int> > &queries
    ) {
        vector adj(numCourses, vector(numCourses, false));

        for (auto &link: prerequisites) adj[link[0]][link[1]] = true;

        // Warshall
        for (int k = 0; k < numCourses; ++k) {
            for (int i = 0; i < numCourses; ++i) {
                if (adj[i][k]) {
                    for (int j = 0; j < numCourses; ++j) {
                        if (adj[k][j]) adj[i][j] = true;
                    }
                }
            }
        }

        const int n = static_cast<int>(queries.size());
        vector ans(n, false);
        for (int i = 0; i < n; ++i) ans[i] = adj[queries[i][0]][queries[i][1]];
        return ans;
    }

复杂度分析：

• 时间复杂度：Warshall算法时间复杂度为O（n^3）占主体，总时间复杂度为O（n^3）
• 空间复杂度：邻接矩阵和可达性矩阵使用同一片O（n^2）空间，空间复杂度总计为O(n^2)