LeetCode#207. 课程表

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。 示例 2:

输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/course-schedule 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：判断有咩有环，可以使用拓扑排序，也可以使用深度遍历，深度遍历需要标记，需要三种标记，需要剪枝，访问到已经访问过的没有问题的就可以直接返回

class Solution { public: bool canFinish1(int numCourses, vector<vector<int>>& prerequisites) { //这样写的时间复杂度是O(n+m) //空间复杂度是O（N+M）N是节点数，M是边的数量 //邻接表就需要O（N+M）来存，左边N个，右边M个 if(numCourses < 2 || prerequisites.size() == 0) return true; //构建一张邻接表 //构建入度表 map<int,vector<int>> G; map<int,int> indegree; int count = 0; for(int i=0;i<prerequisites.size();i++){ //c++部分会自动进行初始化，不需要很多额外判断是否存在 G[prerequisites[i][1]].push_back(prerequisites[i][0]); indegree[prerequisites[i][0]]++; } //将零入度点入栈 stack<int> zeroStack; for(int i=0;i<numCourses;i++){ if(indegree.find(i) == indegree.end() || indegree[i] == 0){ zeroStack.push(i); } } while(!zeroStack.empty()){ int node = zeroStack.top(); count++;//统计拓扑的节点 zeroStack.pop(); for(auto &num:G[node]){ //对其中所有的节点的入度-- indegree[num]--; if(indegree[num] == 0){ zeroStack.push(num); } } } return count == numCourses; } //使用dfs bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { //使用dfs的时间复杂度是O(n+m) //因为每个节点也是去访问它的相邻节点，也就是起对应的m边值 //然后访问过的也不用再次访问了，所以是O(n+m) //空间复杂度也是O(n+m) //需要构建邻接表，入度数组以及标记数组 map<int,vector<int>> G; //标记数组，0表示尚未访问，1表示当前正在访问，-1表示访问完毕 //必须要有-1，否则不是环也会返回false的 vector<int> flag(numCourses,0); for(int i = 0;i < prerequisites.size();i++){ G[prerequisites[i][0]].push_back(prerequisites[i][1]); } for(int i=0;i<numCourses;i++){ if(!dfs(i,G,flag)) return false; } return true; } bool dfs(int node,map<int,vector<int>>& G,vector<int>& flag){ if(flag[node] == -1){ //说明已经被其他节点访问过并且没有环，就不用再访问了 return true; } if(flag[node] == 1){ //表示访问过了,那么就成环了 return false; } flag[node] = 1; for(auto& num : G[node]){ if(!dfs(num,G,flag)) return false; } //访问完成后设置为-1 flag[node] = -1; return true; } };