杭州拱墅区做网站,网站关键词怎么添加,网站怎么做付费项目,小程序外包公司深度优先搜索
思路#xff1a; 课程看作节点#xff0c;依赖关系看作是有向边#xff0c;整体是一个有向图#xff1b;要学完所有课程#xff0c;则需要有向图中不存在相互依赖#xff0c;即不存在环#xff1b;依次遍历课程#xff0c;如果课程状态依赖未解决#x…深度优先搜索
思路 课程看作节点依赖关系看作是有向边整体是一个有向图要学完所有课程则需要有向图中不存在相互依赖即不存在环依次遍历课程如果课程状态依赖未解决则深度搜索其依赖课程状态直到没有依赖能够确定状态再回溯上层被依赖课程在搜索过程中的状态迁移 初始状态 0开始搜索状态 1表示开始处理该课程的状态确定状态 2表示不依赖其他课程或者依赖的课程已经确定不依赖其他课程在搜索的过程中如果其对应的目标课程也进入搜索状态表明存在相互依赖形成环了使用一个变量标记是否有环一旦有环则结束使用一个数组记录课程的搜索状态将课程的依赖关系调整成以依赖的课程为 key目标课程为 value 的哈希表
class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {edges.resize(numCourses);visited.resize(numCourses);for (const auto info: prerequisites) {edges[info[1]].push_back(info[0]);}for (int i 0; i numCourses valid; i) {if (visited[i] 0) {dfs(i);}}return valid;}private:void dfs(int u) {// to searchvisited[u] 1;for (int v: edges[u]) {// init stateif (visited[v] 0) {dfs(v);if (!valid) {return;}} else if (visited[v] 1) {// ringvalid false;return;}}// searchedvisited[u] 2;}private:std::vectorstd::vectorint edges;std::vectorint visited;bool valid true;
};
