力扣207. 课程表

本文主要是介绍力扣207. 课程表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

深度优先搜索

• 思路：
  • 课程看作节点，依赖关系看作是有向边，整体是一个有向图；
  • 要学完所有课程，则需要有向图中不存在相互依赖，即不存在环；
  • 依次遍历课程，如果课程状态依赖未解决，则深度搜索其依赖课程状态，直到没有依赖能够确定状态，再回溯上层被依赖课程，在搜索过程中的状态迁移：
    • 初始状态 0；
    • 开始搜索状态 1，表示开始处理该课程的状态；
    • 确定状态 2，表示不依赖其他课程，或者依赖的课程已经确定不依赖其他课程；
  • 在搜索的过程中，如果其对应的目标课程也进入搜索状态，表明存在相互依赖，形成环了；
  • 使用一个变量标记是否有环，一旦有环则结束；
  • 使用一个数组记录课程的搜索状态；
  • 将课程的依赖关系调整成以依赖的课程为 key，目标课程为 value 的哈希表；

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& 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::vector<std::vector<int>> edges;std::vector<int> visited;bool valid = true;
};

这篇关于力扣207. 课程表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---