10.1 10.3 图DFS 中等 207 Course Schedule 210 Course Schedule Ⅱ

207 Course Schedule

在这里插入图片描述

class Solution {
public:bool hasCycle(int course ,unordered_map<int,vector<int>>& graph,vector<int>& visitStatus){//正在访问的结点再次被访问，存在环if(visitStatus[course] == 1)return true;//该结点已经被访问了且没有环，访问完毕了if(visitStatus[course] == 2)return false;//标记正在被访问的结点visitStatus[course] = 1;for(int pre : graph[course]){if(hasCycle(pre , graph ,visitStatus)){return true;}}//所有结点访问完毕，且不存在环，标记为2visitStatus[course] = 2;return false;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//这道题是关于图的问题，不能存在环//使用数组进行保存//创建图，由于后序需要DFS查找，使用哈希表更为方便unordered_map<int,vector<int>> graph;for(const auto& pair : prerequisites){graph[pair[0]].push_back(pair[1]);}//创建访问数组，初始状态为0vector<int> visitStatus(numCourses,0);//遍历每个结点，使用DFS判断是否有环for(int i = 0 ; i < numCourses ;i++){if(hasCycle(i,graph,visitStatus)){return false;}}return true;}
};

210 Course Schedule II

在这里插入图片描述

class Solution {
public:bool DFS(int course,unordered_map<int,vector<int>>& graph ,vector<int>& visitStatus,vector<int>& route){if(visitStatus[course] == 1){//有环return true; }if(visitStatus[course] == 2){//无环不受影响，但也不会继续向下执行return false;  }visitStatus[course] = 1;//判断所有先修课程for(int pre : graph[course]){if(DFS(pre , graph ,visitStatus ,route)){//有环return true;}}visitStatus[course] = 2;//记录路径中route.push_back(course);return false;}vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {//和Ⅰ一致//但是结果需要给出完成课程的过程序号//相当于判断是否有环+找简单路径//简单路径 **先找点** 使用的还是DFSint m = prerequisites.size();//路径记录vector<int> route;if(!m){//没有先序序列，返回1...numCourses-1的vector<int>for(int i = 0 ; i < numCourses;i++){route.push_back(i);}return route;}//找简单路径的过程中，判断是否有环//记录表unordered_map<int,vector<int>> graph;for(const auto& pair: prerequisites){graph[pair[0]].push_back(pair[1]);}//做标记是否走过 0 走过了 1 又走到了 2 vector<int> visitStatus(numCourses,0);for(int i = 0 ; i < numCourses ; i++){if(DFS(i, graph ,visitStatus, route)){return {};}}return route;}
};