207.Course Schedule (M)

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

1.Description(Medium)

There are a total of n courses you have to take, labeled from0ton - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example

Given n =2, prerequisites =[[1,0]] Returntrue

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Given n =2, prerequisites =[[1,0],[0,1]] Returnfalse

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

2.Code

Hints:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

2. There are several ways to represent a graph. For example, the input prerequisites is a graph represented by a list of edges. Is this graph representation appropriate?(如何来表示一个有向图，可以用边来表示，边是由两个端点组成的，用两个点来表示边)

3. Topological Sort via DFS

   • A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

4. Topological sort could also be done via BFS

这道题的本质就是在有向图中检测环.

Version 1: BFS+Adjacency List

BFS的解法，用邻接表表示图（这里的邻接表用List<List<>>表示，而不是List<HashSet<>>,因为Testcase中二维数组有重复的所以用List而不用Set，对于重复的边，它在邻接表中村了两份，同时计算入度时也算了两次）一位数组indegree来表示每个顶点的入度。

我们开始先根据输入来建立这个有向图，同时将入度数组indegree也初始化好。

然后我们定义一个queue变量，将所有入度为0的点放入队列中，

然后开始遍历队列，从graph里遍历其连接的点，每到达一个新节点，将其入度减一，如果此时该点入度为0，则放入队列末尾。

直到遍历完队列中所有的值，若此时还有节点的入度不为0，则说明环存在，返回false，反之则返回true。

 public boolean canFinish(int numCourses, int[][] prerequisites) {
     //Initial the adjacency list
       List<ArrayList<Integer>> adjacencyList=new ArrayList<ArrayList<Integer>>();
       for(int i=0;i<numCourses;i++){
           adjacencyList.add(new ArrayList<Integer>());
       }
       //Create the indegree array
       int[] indegree=new int[numCourses];
       //Fill the adjacencyList
       for(int i=0;i<prerequisites.length;i++){
           int a=prerequisites[i][1];
           int b=prerequisites[i][0];
           adjacencyList.get(a).add(b);
           indegree[b]++;            
       }

       //Initial the queue and push in=0 into queue
       Queue<Integer> queue=new LinkedList<Integer>();
       for(int i=0;i<numCourses;i++){
           if(indegree[i]==0){
               queue.offer(i);
           }
       }

       while(!queue.isEmpty()){
           int current=queue.poll();
           for(Integer node: adjacencyList.get(current)){
               indegree[node]--;
               if(indegree[node]==0){
                   queue.offer(node);
               }
           }            
       }

       for(int i=0;i<numCourses;i++){
           if(indegree[i]!=0)
               return false;
       }
       return true;      
   }

Version 2：BFS+Edge

http://www.jiuzhang.com/solutions/course-schedule/ 遍历时看最后进队列的是不是所有的点来判断。

 public boolean canFinish(int numCourses, int[][] prerequisites) {

    List[] edges = new ArrayList[numCourses];
    int[] degree = new int[numCourses];

    for (int i = 0;i < numCourses; i++)
        edges[i] = new ArrayList<Integer>();

    for (int i = 0; i < prerequisites.length; i++) {
        degree[prerequisites[i][0]] ++ ;
        edges[prerequisites[i][1]].add(prerequisites[i][0]);
    }

    Queue queue = new LinkedList();
    for(int i = 0; i < degree.length; i++){
        if (degree[i] == 0) {
            queue.add(i);
        }
    }

    int count = 0;
    while(!queue.isEmpty()){
        int course = (int)queue.poll();
        count ++;
        int n = edges[course].size();
        for(int i = 0; i < n; i++){
            int pointer = (int)edges[course].get(i);
            degree[pointer]--;
            if (degree[pointer] == 0) {
                queue.add(pointer);
            }
        }
    }

    return count == numCourses;
}

Version 3：DFS

https://www.zybuluo.com/Yano/note/255732

// DFS
    public static boolean canFinish2(int numCourses, int[][] prerequisites) {
        // 参数检查
        if (prerequisites == null) {
            return false;
        }
        int len = prerequisites.length;
        if (numCourses <= 0 || len == 0) {
            return true;
        }
        int[] visit = new int[numCourses];
        // key：course；value：以该course为prerequisites的course
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        // 初始化map
        for (int[] p : prerequisites) {
            if (map.containsKey(p[1])) {
                map.get(p[1]).add(p[0]);
            } else {
                ArrayList<Integer> l = new ArrayList<Integer>();
                l.add(p[0]);
                map.put(p[1], l);
            }
        }
        // dfs
        for (int i = 0; i < numCourses; i++) {
            if (!canFinishDFS(map, visit, i)) {
                return false;
            }
        }
        return true;
    }
    private static boolean canFinishDFS(
            HashMap<Integer, ArrayList<Integer>> map, int[] visit, int i) {
        if (visit[i] == -1) {
            return false;
        }
        if (visit[i] == 1) {
            return true;
        }
        visit[i] = -1;
        // course i是某些course的prerequisites
        if (map.containsKey(i)) {
            for (int j : map.get(i)) {
                if (!canFinishDFS(map, visit, j)) {
                    return false;
                }
            }
        }
        visit[i] = 1;
        return true;
    }

Version 4: DFS https://labuladong.github.io/algo/2/19/35/

题目应该不难理解，什么时候无法修完所有课程？当存在循环依赖的时候。

其实这种场景在现实生活中也十分常见，比如我们写代码 import 包也是一个例子，必须合理设计代码目录结构，否则会出现循环依赖，编译器会报错，所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。

看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

具体来说，我们首先可以把课程看成「有向图」中的节点，节点编号分别是 0, 1, ..., numCourses-1，把课程之间的依赖关系看做节点之间的有向边。

比如说必须修完课程 1 才能去修课程 3，那么就有一条有向边从节点 1 指向 3。

所以我们可以根据题目输入的 prerequisites 数组生成一幅类似这样的图：

如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。

好，那么想解决这个问题，首先我们要把题目的输入转化成一幅有向图，然后再判断图中是否存在环。

如何转换成图呢？我们前文 图论基础 写过图的两种存储形式，邻接矩阵和邻接表。

以我刷题的经验，常见的存储方式是使用邻接表，比如下面这种结构：

List<Integer>[] graph;

graph[s] 是一个列表，存储着节点 s 所指向的节点。

所以我们首先可以写一个建图函数：

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 图中共有 numCourses 个节点
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : prerequisites) {
        int from = edge[1];
        int to = edge[0];
        // 修完课程 from 才能修课程 to
        // 在图中添加一条从 from 指向 to 的有向边
        graph[from].add(to);
    }
    return graph;
}

图建出来了，怎么判断图中有没有环呢？

先不要急，我们先来思考如何遍历这幅图，只要会遍历，就可以判断图中是否存在环了。

前文 图论基础 写了 DFS 算法遍历图的框架，无非就是从多叉树遍历框架扩展出来的，加了个 visited 数组罢了：

// 防止重复遍历同一个节点
boolean[] visited;
// 从节点 s 开始 DFS 遍历，将遍历过的节点标记为 true
void traverse(List<Integer>[] graph, int s) {
    if (visited[s]) {
        return;
    }
    /* 前序遍历代码位置 */
    // 将当前节点标记为已遍历
    visited[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    /* 后序遍历代码位置 */
}

那么我们就可以直接套用这个遍历代码：

// 防止重复遍历同一个节点
boolean[] visited;

boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    
    visited = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {
        traverse(graph, i);
    }
}

void traverse(List<Integer>[] graph, int s) {
    // 代码见上文
}

注意图中并不是所有节点都相连，所以要用一个 for 循环将所有节点都作为起点调用一次 DFS 搜索算法。

这样，就能遍历这幅图中的所有节点了，你打印一下 visited 数组，应该全是 true。

前文 学习数据结构和算法的框架思维 说过，图的遍历和遍历多叉树差不多，所以到这里你应该都能很容易理解。

现在可以思考如何判断这幅图中是否存在环。

我们前文 回溯算法核心套路详解 说过，你可以把递归函数看成一个在递归树上游走的指针，这里也是类似的：

你也可以把 traverse 看做在图中节点上游走的指针，只需要再添加一个布尔数组 onPath 记录当前 traverse 经过的路径：

boolean[] onPath;

boolean hasCycle = false;
boolean[] visited;

void traverse(List<Integer>[] graph, int s) {
    if (onPath[s]) {
        // 发现环！！！
        hasCycle = true;
    }
    if (visited[s]) {
        return;
    }
    // 将节点 s 标记为已遍历
    visited[s] = true;
    // 开始遍历节点 s
    onPath[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 节点 s 遍历完成
    onPath[s] = false;
}

这里就有点回溯算法的味道了，在进入节点 s 的时候将 onPath[s] 标记为 true，离开时标记回 false，如果发现 onPath[s] 已经被标记，说明出现了环。

PS：参考贪吃蛇没绕过弯儿咬到自己的场景。

这样，就可以在遍历图的过程中顺便判断是否存在环了，完整代码如下：

// 记录一次 traverse 递归经过的节点
boolean[] onPath;
// 记录遍历过的节点，防止走回头路
boolean[] visited;
// 记录图中是否有环
boolean hasCycle = false;

boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    
    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];
    
    for (int i = 0; i < numCourses; i++) {
        // 遍历图中的所有节点
        traverse(graph, i);
    }
    // 只要没有循环依赖可以完成所有课程
    return !hasCycle;
}

void traverse(List<Integer>[] graph, int s) {
    if (onPath[s]) {
        // 出现环
        hasCycle = true;
    }
    
    if (visited[s] || hasCycle) {
        // 如果已经找到了环，也不用再遍历了
        return;
    }
    // 前序遍历代码位置
    visited[s] = true;
    onPath[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 后序遍历代码位置
    onPath[s] = false;
}

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 代码见前文
}

这道题就解决了，核心就是判断一幅有向图中是否存在环。

不过如果出题人继续恶心你，让你不仅要判断是否存在环，还要返回这个环具体有哪些节点，怎么办？

你可能说，onPath 里面为 true 的索引，不就是组成环的节点编号吗？

不是的，假设下图中绿色的节点是递归的路径，它们在 onPath 中的值都是 true，但显然成环的节点只是其中的一部分：

这个问题留给大家思考，我会在公众号留言区置顶正确的答案