AlgoPress | AlgoPress

题目描述

https://leetcode.cn/problems/course-schedule

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

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

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

示例 1：

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

示例 2：

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

提示：

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

思路1:直接递归

遍历课程开始学习，深度优先，先学习依赖的学科。如果出现循环依赖，则不能完成学科，我们深度搜索的时候，增加一个 deep 参数，用来表示调用的深度，如果大于学科总科数，说明出现了循环依赖。

参考代码

csharp

public class Solution {

    bool[] learn;

    private bool dfs(int[][] prerequisites, int index, int deep){
        if(deep > prerequisites.Length){
            return false;
        }
        //如果学习过了，直接返回 true
        if(learn[index]){
            return true;
        }
        //检查依赖
        for(int i=0; i<prerequisites.Length; i++){
            if(prerequisites[i][0] == index){
                //先学习依赖学科
                if(!dfs(prerequisites,prerequisites[i][1], deep+1)){
                    return false;
                }
            }
        }
        //没有依赖
        learn[index] = true;
        return true;
    }

    public bool CanFinish(int numCourses, int[][] prerequisites) {
        //思路：从第一门课开始，如果需要选修其他，就先学习其他科，然后将自己标记为 true
        //如果中间有循环依赖，则他们dfs跳转的次数将大于总课程数，返回 false，则无法修完所有的课
        learn = new bool[numCourses];
        for(int i=0; i<numCourses; i++){
            if(!dfs(prerequisites,i,0)){
                return false;
            }
        }
        return true;
    }
}

思路2:拓扑排序 DFS

上述通过增加次数来得到图中循环依赖。

我们也可以通过设置节点的状态来直到是否存在循环依赖。设置每个课程为一个节点，它有3种状态。

未搜索 : 0
搜索中 : 1
已完成 : 2

如果课程状态是0的，就进入搜索，设置为1. 当搜索过程中递归，如果发现需要的课程已经设置为1了，那么说明出现了循环依赖，此时设置 valid 为 false

csharp

public class Solution{
    IList<IList<int>> edges;
    int[] visited;
    bool valid = true;

    public bool CanFinish(int numCourses, int[][] prerequisites){
        edges = new List<IList<int>>();
        for(int i=0; i<numCourses; i++){ //每门课程设置一个依赖列表
            edges.Add(new List<int>());
        }

        visited = new int[numCourses];
        for(int i = 0; i<prerequisites.Length; i++){
            edges[prerequisites[i][1]].Add(prerequisites[i][0]); //将依赖课程加入进去
        }

        //开始遍历学习课程
        for(int i=0; i < numCourses && valid; i++){
            if(visited[i] == 0){
                dfs(i);
            }
        }

        return valid;
    }

    private void dfs(int index){
        visited[index] = 1; //设置访问状态
        for(int i=0; i<edges[index].Count; i++ ){ //遍历它的依赖
            int req = edges[index][i];

            if(visited[req] == 0){
                dfs(req);
                if(!valid){
                    return;
                }
            }
            else if(visited[req] == 1){
                valid = false;
                return;
            }
        }
        visited[index] = 2;
    }

思路3:拓扑排序 BFS

csharp

public class Solution{

    IList<IList<int>> edges;

    public bool CanFinish(int numCourses, int[][] prerequisites){
        edges = new List<IList<int>>();
        for(int i=0; i<numCourses; i++){
            edges.Add(new List<int>());
        }
        //添加依赖课程
        for(int i=0; i<prerequisites.Length; i++){
            edges[prerequisites[i][1]].Add(prerequisites[i][0]);
        }
        //将入度为0的课程加入queue中
        Queue<int> queue = new Queue<int>();
        for(int i=0; i<edges.Count; i++){
            if(edges[i].Count == 0){
                queue.Enqueue(i);
            }
        }
        //依次学习课程
        while(queue.Count > 0){
            int index = queue.Dequeue();
            for(int i=0; i<edges.Count; i++){
                if(edges[i].Contains(index)){
                    edges[i].Remove(index);
                    if(edges[i].Count == 0){
                        queue.Enqueue(i);
                    }
                }
            }
        }
        //判断是否还有课程没学
        for(int i=0; i<edges.Count; i++){
            if(edges[i].Count > 0){
                return false;
            }
        }
        return true;
    }
}

题目描述 #

思路1:直接递归 #

参考代码 #

思路2:拓扑排序 DFS #

思路3:拓扑排序 BFS #

题目描述

思路1:直接递归

参考代码

思路2:拓扑排序 DFS

思路3:拓扑排序 BFS