【LeetCode207.课程表】以及变式

题目链接

207. 课程表 - 力扣（LeetCode）

实现思路

1. 用一个二维数组存邻接表，存储的是某个课程的下一门课程的集合；
2. 用一个数组存储每门课程的入度，也就是如果某门课程需要另外一门先修课程，入度就+1；
3. 用一个队列，存储当前入度为0的课程，也就是可以修的课程x，每次循环，判断x作为哪些课程的先修课程，那么这门课程的入度-1，如果为0，这门课程也可以修了，加入队列中；
4. 最后，判断完成的课程数是否和总课程数相等。

代码实现

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 构造邻接表vector<vector<int>> edges(numCourses);// 统计入度vector<int> indegree(numCourses, 0);for (int i = 0; i < prerequisites.size(); i++) {int x = prerequisites[i][0];int y = prerequisites[i][1];edges[x].push_back(y);indegree[y]++;}int finish = 0;queue<int> q;for (int i = 0; i < numCourses; i++) {if (!indegree[i]) {finish++;q.push(i);}}while (q.size()) {int x = q.front();q.pop();for (int y : edges[x]) {indegree[y]--;if (!indegree[y]) {finish++;q.push(y);}}}return finish == numCourses;}
};

变式

题目解析

如果已经修好的课程是通过另外一个数组传入的，也就是说，如果仅仅给出修课条件[[1,0]]，那么0，1两门课都不能修，但是如果已经修好的课程数组为[0]，那么0，1就都可以修。（限制：不存在循环依赖的情况，也就是0的先修课程是1，1的先修课程是0的情况）。

实现思路

• 在之前的代码上，增加一个判断，就是如果不在已经学习的集合中，那么就算通过邻接图的入度为0，也要手动将入度设置为1。

代码实现

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites, set<int>& learned) {// 构造邻接表vector<vector<int>> edges(numCourses);// 统计入度vector<int> indegree(numCourses, 0);for (int i = 0; i < prerequisites.size(); i++) {int x = prerequisites[i][0];int y = prerequisites[i][1];edges[x].push_back(y);indegree[y]++;}// 新增：只有在learned数组中的课程，入度才是0，否则若原来是0的需要改为1for (int i = 0; i < numCourses; i++) {if (!indegree[i] && !learned.count(i)) {indegree[i] = 1;}}int finish = 0;queue<int> q;for (int i = 0; i < numCourses; i++) {if (!indegree[i]) {finish++;q.push(i);}}while (q.size()) {int x = q.front();q.pop();for (int y : edges[x]) {indegree[y]--;if (!indegree[y]) {finish++;q.push(y);}}}return finish == numCourses;}
};