题目主要信息

为了毕业你需要选择 n 门课程，这 n 门课程中存在一定的依赖关系，例如想要完成 B 课程，必须先完成 A 课程，请你找出一个可以完成全部课程的顺序，如果无论如何选择都无法完成全部课程则返回空数组。

依赖关系以如下方式输入：

[[2,1],[3,2]]

即要完成课程 2 ，必须先完成 1 ， 要完成课程 3 ，必须先完成课程 2，答案 [1,2,3] 即可。

但也可能出现类似

[[2,1],[1,2]]

要完成课程 2 ，必须先完成 1 ，要完成课程 1 ，必须先完成课程 1 ，则无解，返回一个空数组即可。

方法一：DFS

具体方法

搜索到了节点$startstart$，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把$startstart$入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于$startstart$ 处于栈顶的位置，那么 $startstart$ 出现在所有$startstart$的相邻节点的前面。因此对于$startstart$ 这个节点而言，它是满足拓扑排序的要求的。

这样以来，我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。

给每个节点设置三种状态，未访问、访问中和完成访问。

从未访问的节点$startstart$可以$dfsdfs$搜索，遍历该节点的每一个相邻节点$endend$

• 如果$end\mathrm{为}end为$「未搜索」，开始搜索$endend$，待搜索完成回溯到 $startstart$；
• 如果$end\mathrm{为}end为$「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；
• 如果$end\mathrm{为}end为$「已完成」，那么说明end已经在栈中了，而 $startstart$还不在栈中，因此$startstart$无论何时入栈都不会影响到 $(start,end)(start,end)$ 之前的拓扑关系，以及不用进行任何操作。

当 start的所有相邻节点都为「已完成」时，将 $startstart$放入栈中，并将其标记为「已完成」。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型二维数组 
     * @param n int整型 
     * @return int整型一维数组
     */
    // 存节点的临接节点
    List<List<Integer>> list = new ArrayList<>();
    // 标识当前节点状态 0表示未访问 1表示访问中 2表示访问完成
    int []visit;
    // 最终的结果
    int [] result;
    // 索引
    int index ;
    // 判断有向图中是否有环
    boolean valid = true;
    public int[] findOrder (int[][] prerequisites, int n) {
        // write code here
               // 初始化
        result = new int[n];
        visit = new int[n];
        index = n-1;
        // 节点的邻接节点初始化
        for(int i = 0;i < n ;i++){
            list.add(new ArrayList<>());
        }
        // 将节点的临接节点存入list中
        for(int []num : prerequisites){
            int start = num[1],end = num[0];
            // 起点为start 终点节点为end
            list.get(start).add(end);
        }

        // 遍历每一个未搜索的节点
        for(int i= 0 ;i < n && valid;i++){
            if(visit[i] == 0)
                dfs(i);
        }
        if (!valid) {
            return new int[0];
        }
        // 如果没有环，那么就有拓扑排序
        return result;
    }
       public void dfs(int start){
        // 当前节点访问中
        visit[start] = 1;
        // 遍历当前节点的相邻节点
        for(int end : list.get(start)){
            if(visit[end] == 0){
                dfs(end);
                if(!valid)
                    return;
            }
            // 如果「搜索中」说明找到了环
            else if (visit[end] == 1) {
                valid = false;
                return;
            }
        }
        // start节点相邻节点已经访问完
        visit[start] = 2;
        result[index--] = start;
    }
}

复杂度分析

时间复杂度：$O\mathrm{（}m+n\mathrm{）}O（m+n）$，$n\mathrm{为}\mathrm{课}\mathrm{程}\mathrm{数}\mathrm{，}m\mathrm{为}\mathrm{先}\mathrm{修}\mathrm{课}\mathrm{程}\mathrm{数}n为课程数，m为先修课程数$

空间复杂度：$O\mathrm{（}m+n\mathrm{）}O（m+n）$题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为$O\mathrm{（}m+n\mathrm{）}O（m+n）$

方法二：BFS

具体方法

使用正向思维，顺序地生成拓扑排序，这种方法也更加直观。

用一个队列来进行广度优先搜索。开始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，取出队首的节点 start：

• 将 start放入答案中；
• 移除 start的所有出边，也就是将start 的所有相邻节点的入度减少 1。如果某个相邻节点end 的入度变为 0，将end 放入队列中。

在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型二维数组 
     * @param n int整型 
     * @return int整型一维数组
     */
    public int[] findOrder (int[][] prerequisites, int n) {
        // write code here
                // 记录节点的相邻节点
        List<List<Integer>> list = new ArrayList<>();
        // 存储每个节点的入度
        int[] indeg = new int[n];
        // 最终的结果
        int []result = new int[n];
        int index = 0;

        // 将节点存入list中
        for(int i = 0;i < n ;i++){
            list.add(new ArrayList<>());
        }
        // 处理节点的相邻节点
        for(int []num:prerequisites){
            int start = num[1],end = num[0];
            list.get(start).add(end);
            // 节点end的入度加一
            ++indeg[end];
        }
        // 使用一个队列
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0;i<n;i++){
            if(indeg[i] == 0)
                queue.offer(i);
        }

        while(!queue.isEmpty()){
            int start = queue.poll();
            result[index++] = start;
            for(int end : list.get(start)){
                // 节点入度-1
                --indeg[end];
                // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if (indeg[end] == 0) {
                    queue.offer(end);
                }
            }
        }
        if(index == n)
            return result;
        return new int[0];
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}m+n\mathrm{）}O（m+n）$，n为课程数，m为先修课程数
• 空间复杂度：$O\mathrm{（}m+n\mathrm{）}O（m+n）$题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为$O\mathrm{（}m+n\mathrm{）}O（m+n）$