LeetCode每日一题 207. 课程表

题目描述

给定一个整数 numCourses 表示一学期必须选修的课程数目，以及一个课程先修关系数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示如果要学习课程 ai 则必须先学习课程 bi。判断是否可能完成所有课程的学习，如果可以，返回 true；否则，返回 false。

算法思路

这个问题可以通过拓扑排序来解决，拓扑排序是一种对有向无环图（DAG）进行排序的方法。如果存在一种合法的学习顺序，那么图中一定不存在环。以下是解决这个问题的步骤：

1. 创建一个有向图 graph，以及一个入度数组 inDegree。

2. 遍历 prerequisites 数组，将课程之间的先修关系构建成有向边，同时更新每门课程的入度。

3. 将入度为0的课程入队，这些课程可以作为起始节点进行拓扑排序。

4. 在循环中，依次将入度为0的课程出队，并更新与它相邻的课程的入度。如果更新后的入度为0，将该课程入队。

5. 继续循环，直到队列为空。如果拓扑排序过程中没有出现环（即剩余的课程数为0），则可以完成所有课程学习，返回 true；否则返回 false。

代码实现

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> inDegree(numCourses, 0);

        // 构建有向图和入度数组
        for (const vector<int>& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            inDegree[pre[0]]++;
        }

        queue<int> q;

        // 将入度为0的课程入队
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            numCourses--;

            // 更新与当前课程相邻的课程的入度
            for (int neighbor : graph[curr]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return numCourses == 0;
    }
};