#yyds干货盘点# LeetCode程序员面试金典：课程表 II

1.简述：

现在你总共有了 numCourses 需要选择门课，记0到numCourseseses - 1.给你一个数组prerquisiteses ，其中 prerequisites[i] = [ai, bi] ，在选修课上表示 ai 前 必须 先选修bi 。

例如，想学习课程 0 ，你需要先完成课程1 ，我们用匹配来表示：[0，1] 。

返回所有课程安排的学习顺序。可能有多个正确的顺序，你只需要返回 任意一种 没关系。如果不可能完成所有课程，请返回 一个空数组 。

示例 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]

2.实现代码：

class Solution {    // 存储有向图    List<List<Integer>> edges;    // 标记每个节点的状态：0=未搜索，1=搜索，2=已完成    int[] visited;    // 用数组模拟栈，下标 n-1 为栈底，0 为栈顶    int[] result;    // 判断向图中是否有环。    boolean valid = true;    // 栈下标    int index;    public int[] findOrder(int numCourses, int[][] prerequisites) {        edges = new ArrayList<List<Integer>>();        for (int i = 0; i < numCourses; ++i) {            edges.add(new ArrayList<Integer>());        }        visited = new int[numCourses];        result = new int[numCourses];        index = numCourses - 1;        for (int[] info : prerequisites) {            edges.get(info[1]).add(info[0]);        }        // 每次选一个「未搜索」的节点，开始深度优先搜索        for (int i = 0; i < numCourses && valid; ++i) {            if (visited[i] == 0) {                dfs(i);            }        }        if (!valid) {            return new int[0];        }        // 假如没有环，然后就有拓扑排序了        return result;    }    public void dfs(int u) {        // 将节点标记为「搜索中」        visited[u] = 1;        // 搜索相邻节点        // 只要发现有环，立即停止搜索        for (int v: edges.get(u)) {            // 如果「未搜索」然后搜索相邻节点            if (visited[v] == 0) {                dfs(v);                if (!valid) {                    return;                }            }            // 如果「搜索中」说明找到了环            else if (visited[v] == 1) {                valid = false;                return;            }        }        // 将节点标记为「已完成」        visited[u] = 2;        // 将节点入栈        result[index--] = u;    }}