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; }}
![](/images/780-200-2.jpg)