题目:210.课程表 II
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 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]- 提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同思路
这个问题可以抽象为一个有向图问题，课程是图中的节点，先修关系是图中的边。我们需要判断这个图中是否存在环。如果存在环，则说明有些课程之间存在循环依赖，无法完成所有课程。如果不存在环，则可以完成所有课程。可以通过 DFS检测环 来解决这个问题。
- 构建图：将每门课程作为节点，每个先修关系作为有向边。
prerequisites[i] = [ai, bi]表示必须先学bi之后才能学ai，即bi -> ai。 - DFS检测环： 使用
DFS遍历每个节点，构建递归调用栈。如果在DFS过程中遇到已经在当前递归路径上的节点，则说明存在环，返回true，否则访问结束以后将课程加入结果列表，返回false。 - 返回结果：如果遍历完所有节点，没有检测到环，则对结果列表进行倒序排序并转换为数组，返回排序后的结果数组，否则返回空数组。
- 时间复杂度:O(m+n)，其中 m 是课程数量，n 是先修课程的依赖关系数量。
- 时间复杂度:O(m+n)，其中 m 是课程数量，n 是先修课程的依赖关系数量。
代码
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer> resultList = new ArrayList<>();
List<List<Integer>> graph = buildGraph(numCourses, prerequisites);
// 状态数组，0 表示未访问，1 表示当前路径访问中，-1 表示已经访问完毕
int[] visited = new int[numCourses];
// 遍历图，检测是否存在环
for (int i = 0; i < numCourses; i++) {
if (dfs(visited, i, graph, resultList)) {
// 存在环，不能完成所有课程的学习
return new int[0];
}
}
// 对结果列表进行倒序排序并转换为数组
int[] result = new int[numCourses];
for (int i = 0; i < resultList.size(); i++) {
result[resultList.size() - i - 1] = resultList.get(i);
}
// 不存在环，可以完成所有课程的学习
return result;
}
// 深度优先搜索，判断是否存在环，true 表示存在环
private boolean dfs(int[] visited, int course, List<List<Integer>> graph, List<Integer> resultList) {
// 发现环
if (visited[course] == 1) {
return true;
}
// 该节点已经安全访问过
if (visited[course] == -1) {
return false;
}
// 标记当前节点为访问中
visited[course] = 1;
// 获取当前节点的下一个节点列表
List<Integer> nextCourses = graph.get(course);
for (Integer nextCourse : nextCourses) {
if (dfs(visited, nextCourse, graph, resultList)) {
return true;
}
}
// 访问结束，标记为已访问
visited[course] = -1;
// 将课程加入结果列表
resultList.add(course);
return false;
}
// 将等式转换成图的邻接表
private List<List<Integer>> buildGraph(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
int start = prerequisite[1];
int end = prerequisite[0];
graph.get(start).add(end);
}
return graph;
}
