210.Course Schedule II (M)

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

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example

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

Given n = 4, prerequisites =[1,0],[2,0],[3,1],[3,2]] Return[0,1,2,3]or[0,2,1,3]

2.Code

Version 1: BFS

这道题我们得找出要上的课程的顺序，即有向图的拓扑排序.

此题正是基于之前解法的基础上稍加修改，我们从queue中每取出一个数就将其存在结果中，最终若有向图中有环，则结果中元素的个数不等于总课程数，那我们将结果清空即可(注意设置一个数组存放结果还有一个index去存放进数组的位置)

 public int[] findOrder(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);
            }
        }


        int [] result=new int[numCourses];
        //count is for identifying index of node
        int index=0;

        while(!queue.isEmpty()){
            int current=queue.poll();
            result[index]=current;
            index++;

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

        if(index==numCourses){
            return result;
        }
        return new int[0];      
    }

Version 2: Topological Sort https://labuladong.github.io/algo/2/19/35/

先说一下拓扑排序（Topological Sorting）这个名词，网上搜出来的定义很数学，这里干脆用百度百科的一幅图来让你直观地感受下：

直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的，比如上图所有箭头都是朝右的。

很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。

但是我们这道题和拓扑排序有什么关系呢？

其实也不难看出来，如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序。

首先，我们先判断一下题目输入的课程依赖是否成环，成环的话是无法进行拓扑排序的，所以我们可以复用上一道题的主函数：

public int[] findOrder(int numCourses, int[][] prerequisites) {
    if (!canFinish(numCourses, prerequisites)) {
        // 不可能完成所有课程
        return new int[]{};
    }
    // ...
}

那么关键问题来了，如何进行拓扑排序？是不是又要秀什么高大上的技巧了？

其实特别简单，将后序遍历的结果进行反转，就是拓扑排序的结果。

直接看解法代码吧，在上一题环检测的代码基础上添加了记录后序遍历结果的逻辑：

// 记录后序遍历结果
List<Integer> postorder = new ArrayList<>();
// 记录是否存在环
boolean hasCycle = false;
boolean[] visited, onPath;

// 主函数
public int[] findOrder(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);
    }
    // 有环图无法进行拓扑排序
    if (hasCycle) {
        return new int[]{};
    }
    // 逆后序遍历结果即为拓扑排序结果
    Collections.reverse(postorder);
    int[] res = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        res[i] = postorder.get(i);
    }
    return res;
}

// 图遍历函数
void traverse(List<Integer>[] graph, int s) {
    if (onPath[s]) {
        // 发现环
        hasCycle = true;
    }
    if (visited[s] || hasCycle) {
        return;
    }
    // 前序遍历位置
    onPath[s] = true;
    visited[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 后序遍历位置
    postorder.add(s);
    onPath[s] = false;
}

// 建图函数
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;
}

代码虽然看起来多，但是逻辑应该是很清楚的，只要图中无环，那么我们就调用 traverse 函数对图进行 DFS 遍历，记录后序遍历结果，最后把后序遍历结果反转，作为最终的答案。

那么为什么后序遍历的反转结果就是拓扑排序呢？

我这里也避免数学证明，用一个直观地例子来解释，我们就说二叉树，这是我们说过很多次的二叉树遍历框架：

void traverse(TreeNode root) {
    // 前序遍历代码位置
    traverse(root.left)
    // 中序遍历代码位置
    traverse(root.right)
    // 后序遍历代码位置
}

二叉树的后序遍历是什么时候？遍历完左右子树之后才会执行后序遍历位置的代码。换句话说，当左右子树的节点都被装到结果列表里面了，根节点才会被装进去。

后序遍历的这一特点很重要，之所以拓扑排序的基础是后序遍历，是因为一个任务必须在等到所有的依赖任务都完成之后才能开始开始执行。

你把每个任务理解成二叉树里面的节点，这个任务所依赖的任务理解成子节点，那你是不是应该先把所有子节点处理完再处理父节点？这是不是就是后序遍历？

再说一说为什么还要把后序遍历结果反转，才是最终的拓扑排序结果。

我们说一个节点可以理解为一个任务，这个节点的子节点理解为这个任务的依赖，但你注意我们之前说的依赖关系的表示：如果做完 A 才能去做 B，那么就有一条从 A 指向 B 的有向边，表示 B 依赖 A。

那么，父节点依赖子节点，体现在二叉树里面应该是这样的：

是不是和我们正常的二叉树指针指向反过来了？所以正常的后序遍历结果应该进行反转，才是拓扑排序的结果。

以上，我简单解释了一下为什么「拓扑排序的结果就是反转之后的后序遍历结果」，当然，我的解释虽然比较直观，但并没有严格的数学证明，有兴趣的读者可以自己查一下。

总之，你记住拓扑排序就是后序遍历反转之后的结果，且拓扑排序只能针对有向无环图，进行拓扑排序之前要进行环检测，这些知识点已经足够了。