[LC]210. 课程表 II

🚩传送门：力扣题目

题目

你这个学期必须选修 门课程，记为 到 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 给出，其中 ，表示如果要学习课程 则 必须 先学习课程 。例如，先修课程对表示：想要学习课程 ，你需要先完成课程 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]] 输出：[0,1] 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 输出：[0,2,1,3] 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = [] 输出：[0]

解题思路：拓扑排序

拓扑排序可以深搜（DFS）也可以广搜（BFS）

本题是一道经典的「拓扑排序」问题，给定一个包含 个节点的有向图 ，我们给出它的节点编号的一种排列。
如果满足：对于图中的任意一条有向边， 在排列中都出现在 的前面。那么称该排列是图 的「拓扑排序」。

根据上述的 定义，我们可以得出两个结论：

• 如果图中存在环（即图不是「有向无环图」），那么图不存在拓扑排序。

  这是因为假设图中存在环 ，那么 在排列中必须出现在 的前面，但 同时也必须出现在 的前面，因此无法满足这个要求

• 如果图是有向无环图，那么它的拓扑排序可能不止一种。

  举一个最极端的例子，如果图值包含 个节点却没有任何边，那么任意一种编号的排列都可以作为拓扑排序。

广度搜索

复杂度分析

时间复杂度：，遍历一个图需要访问所有节点和所有临边， 和 分别为节点数量和临边数量；

空间复杂度：，为建立邻接表所需额外空间， 长度为 ，并存储 条临边的数据。

我的代码

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>>edges=new ArrayList<>();
        int[]inedges=new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        // 边和入度
        for (int i = 0; i < prerequisites.length; i++) {
            inedges[prerequisites[i][0]]++;
            edges.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        LinkedList<Integer>queue=new LinkedList<>();
        // 入度为0的结点u入队
        for (int i = 0; i < numCourses; i++) {
            if(inedges[i]==0) queue.addLast(i);
        }
        ArrayList<Integer>res=new ArrayList<>();
        while(!queue.isEmpty()){
            int u=queue.pollFirst();
            res.add(u); // 先学习u
            numCourses--;
            for (int i = 0; i < edges.get(u).size(); i++) {
                int v=edges.get(u).get(i);  // 得到结点v
                inedges[v]--;               //入度减少
                if(inedges[v]==0)queue.addLast(v);
            }
        }
        if(numCourses!=0) res.clear();    // 有环需要返回空数组
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

深度优先搜索

复杂度分析

时间复杂度：，遍历一个图需要访问所有节点和所有临边， 和 分别为节点数量和临边数量；

空间复杂度：，为建立邻接表所需额外空间， 长度为 ，并存储 条临边的数据。

我的代码

import java.util.ArrayList;
import java.util.List;
class Solution {
    boolean valid = true;
    int index;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        index = numCourses - 1;
        List<List<Integer>> edges = new ArrayList<List<Integer>>();
        int[] visited = new int[numCourses];
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        // 添加边的信息
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        // 遍历每一个结点做起始结点开始dfs
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i, visited, edges, res);
            }
        }
        if (!valid) return new int[0];
        return res;
    }
    public void dfs(int u, int[] visited, List<List<Integer>> edges, int[] res) {
        // 正在访问
        visited[u] = 1;
        // 一条由点 u -> v 的边 
        for (int v : edges.get(u)) {
            // 未访问
            if (visited[v] == 0) {
                dfs(v, visited, edges, res);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                // 遇到一条正在访问的边,说明有环,刚才遍历过它
                valid = false;
                return;
            }
        }
        // 完成访问
        visited[u] = 2;
        res[index--] = u;    // 【重点】:递归最底层完成后添加进答案,倒序添加
    }
}