[数据结构与算法]LC207. 课程表

题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
提示：

1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

思路

这是一道拓扑排序题。
想要判断能不能完成课，需要判断某些课程之间会不会形成一个有向环。如果有有向环，则说明无法完成规定的所有课程。

注意：

• 对于课程x,它可能有多个前驱课程。
• prerequisites没有出现的课程说明不需要前驱课程

对于一门课程能不能完成，我们需要查看它的前驱课程能不能完成。
比如[[1,2],[2,3][3,4]],想要知道课程1能不能完成，我们需要知道课程4能不能完成。
如果把上述结构看成一棵树，对于根节点1，我们就需要知道要找它的叶子节点，如果叶子节点均能正常完成，那么根节点也一定能完成。

根据这种思路来看，好像可以采用深度优先搜索来解决。即对于每个课程，判断它的叶子节点能不能完成，如果能完成，再从叶子节点一层一层往上推，直到根节点课程。
同时每次判断可以完成的课程，建立一个备忘录记下他们。这样，后面有些课程进行前驱判断时，可以依照这个备忘录排除一些课程，避免一些子树的重复搜索（也就是借助dp的思想）

代码流程如下：

• 建立相应的标记数据结构：
  • pre数组：记录每个课程i的所有直接相连的前驱课程（如果用哈希表记录，会超时）
  • f数组：判断课程i是在哪种状态
    • 还没进行判断
    • 前驱节点判断中
    • 标记为可以完成的课程
  • valid:标记是否可以完成所有课程
• 遍历0到numCourses-1的所有课程，如果他还没有进行判断，则进入dfs搜索
• 当课程x进入搜索时，首先将f[x]标记为1，表示正在判断中。然后遍历x的所有前驱课程，对于每个前驱课程：
  • 如果没有被判断过，则dfs
  • 如果前驱节点也正在判断中，说明进入了有向环，课程无法完成，valid为false，结束。

代码

class Solution {
public:
    //采用哈希表会超时
    vector<vector<int>> pre;
    vector<int> f;
    bool valid = true;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        pre.resize(numCourses);
        f.resize(numCourses);
        for(auto nums:prerequisites){
            pre[nums[0]].push_back(nums[1]);
        }
        for(int i=0;i<numCourses&&valid;i++){
            if(f[i]==0)
                dfs(i);
        }
        return valid;
    }
    void dfs(int x){
    	//1表示正在搜索它的前驱
        f[x] = 1;
        for(int i=0;i<pre[x].size();i++){
            if(f[pre[x][i]]==0)
                dfs(pre[x][i]);
            if(f[pre[x][i]]==1){
                valid = false;
                return;
            }
        }
        //2表示这门课可以顺利完成
        f[x] = 2;
    }
};