GuilinDev
Lc0210
05 August 2008
210 Course Schedule II
题目
There are a total of n courses you have to take, labeled from 1
0
1
n-1
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: 1
[0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
1
2
3
4
Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
course 0. So the correct course order is [0,1] .
Example 2:
1
2
3
4
5
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
分析
与207相同，只是这道题要求打印出完成课程的顺序，不仅仅是判断是否可以完成。《算法4》中第4.2.4.2小节《寻找有向环》和《拓扑排序》详细解释了做法。
做法依然时BFS（记录入度表）和DFS，可以邻接表或者邻接矩阵，上一道题用的邻接表，这次用邻接矩阵。
代码
BFS
- 建立入度表，入度为 0 的节点先入队
- 当队列不为空，节点出队，标记学完课程数量的变量加 1，并记录该课程
- 将课程的邻居入度减 1
- 若邻居课程入度为 0，加入队列
邻接表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] results = new int[numCourses];
int[] indegrees = new int[numCourses]; // 入度表
List<List<Integer>> adjacency = new ArrayList<>(); //邻接表存储图
//BFS
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
adjacency.add(new ArrayList<>());
}
// 给每门课添加入度，以及将入度信息和课程本身添加到邻接表中
for (int[] pre : prerequisites) {
indegrees[pre[0]]++;
adjacency.get(pre[1]).add(pre[0]);
}
// 将入度为0（没有前置课程的）的课程索引初始化入队
for (int i = 0; i < numCourses; i++) {
if (indegrees[i] == 0) {
queue.offer(i);
}
}
// BFS拓扑排序
int count = 0;
while (!queue.isEmpty()) {
int pre = queue.poll();
results[count] = pre;
count++;
for (int cur : adjacency.get(pre)) { // 当前课程减去入度
indegrees[cur]--;
if (indegrees[cur] == 0) {
queue.offer(cur);
}
}
}
return numCourses == count ? results : new int[]{};
}
}
用一个变量记录学完的课程数量，一个数组记录最终结果，简洁好理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] results = new int[numCourses];
int[] indegrees = new int[numCourses]; //入度表也可以用hashmap表示
// 创建入度表
for (int[] pre : prerequisites) {
indegrees[pre[0]]++; // 把每个入度简化为增加1
}
Queue<Integer> queue = new ArrayDeque<>();
// 首先将入度为0的顶点放进来
for (int i = 0; i < numCourses; i++) { // 课程表用数字表示
if (indegrees[i] == 0) {
queue.offer(i);
}
}
int count = 0; // 记录课程是否全部被修完
while (!queue.isEmpty()) {
int currCourse = queue.poll();
results[count] = currCourse; // 把访问到的顶点（修完的课）加入到结果中
count++;
// 更新剩余未访问的顶点（未修的课）的入度，并将入度为0的课加入到队列中准备访问
for (int[] pre : prerequisites) {
if (pre[1] == currCourse) { // 只用修改依赖课程是当前课程的课程
indegrees[pre[0]]--; // 依赖课程是当前课程的课程的入度--11
if (indegrees[pre[0]] == 0) { // 入度为0则将课程加入到BFS的下一层中
queue.offer(pre[0]);
}
}
}
}
// 检查下全部课程是否都被修完
return count == numCourses ? results : new int[]{};
}
}
DFS
- 建立邻接矩阵
- DFS 访问每一个课程，若存在环直接返回
1) 数组作为邻接矩阵，status 保存课程的访问状态，同一个栈保存课程的访问序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
// 邻接矩阵 + DFS 由于用的数组，每次都要遍历，效率比较低
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses == 0) {
return new int[0];
}
// 建立邻接矩阵
int[][] graph = new int[numCourses][numCourses];
for (int[] p : prerequisites) {
graph[p[1]][p[0]] = 1;
}
// 记录访问状态的数组，访问过了标记 -1，正在访问标记 1，还未访问标记 0
int[] status = new int[numCourses];
Stack<Integer> stack = new Stack<>(); // 用栈保存访问序列
for (int i = 0; i < numCourses; i++) {
if (!dfs(graph, status, i, stack)) return new int[0]; // 只要存在环就返回
}
int[] result = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
result[i] = stack.pop();
}
return result;
}
private boolean dfs(int[][] graph, int[] status, int i, Stack<Integer> stack) {
if (status[i] == 1) { // 当前节点在此次 dfs 中正在访问，说明存在环
return false;
}
if (status[i] == -1) {
return true;
}
status[i] = 1;
for (int j = 0; j < graph.length; j++) {
// dfs 访问当前课程的后续课程，看是否存在环
if (graph[i][j] == 1 && !dfs(graph, status, j, stack)) return false;
}
status[i] = -1; // 标记为已访问
stack.push(i);
return true;
}
}
2) hashset作为邻接矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
// 方法 2 升级版：用 HashSet 作为邻接矩阵，加速查找速度
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses == 0) {
return new int[0];
}
// HashSet 作为邻接矩阵
HashSet<Integer>[] graph = new HashSet[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new HashSet<>();
}
for (int[] p : prerequisites) {
graph[p[1]].add(p[0]);
}
int[] mark = new int[numCourses]; // 标记数组
Stack<Integer> stack = new Stack<>(); // 结果栈
for (int i = 0; i < numCourses; i++) {
if(!isCycle(graph, mark, i, stack)) return new int[0];
}
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = stack.pop();
}
return res;
}
private boolean isCycle(HashSet<Integer>[] graph, int[] mark, int i, Stack<Integer> stack) {
if (mark[i] == -1) {
return true;
}
if (mark[i] == 1) {
return false;
}
mark[i] = 1;
for (int neighbor : graph[i]) {
if (!isCycle(graph, mark, neighbor, stack)) {
return false;
}
}
mark[i] = -1;
stack.push(i);
return true;
}
}