BFS + Topological Sort
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
| class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] inDegrees = new int[numCourses];
Map<Integer, List<Integer>> nodeToNodeList = new HashMap<>();
for (int[] prerequisite : prerequisites) {
int from = prerequisite[1], to = prerequisite[0];
inDegrees[to]++;
nodeToNodeList.computeIfAbsent(from, key -> new ArrayList<>()).add(to);
}
Queue<Integer> zeroInDegreeCourseQueue = new LinkedList<>();
for (int i = 0; i < inDegrees.length; i++) {
if (inDegrees[i] == 0) {
zeroInDegreeCourseQueue.offer(i);
}
}
List<Integer> courseList = new ArrayList<>(numCourses);
while (!zeroInDegreeCourseQueue.isEmpty()) {
int course = zeroInDegreeCourseQueue.poll();
courseList.add(course);
for (int nextCourse : nodeToNodeList.getOrDefault(course, Collections.emptyList())) {
if (--inDegrees[nextCourse] == 0) {
zeroInDegreeCourseQueue.offer(nextCourse);
}
}
}
if (courseList.size() != numCourses) {
return new int[0];
} else {
int[] res = new int[courseList.size()];
for (int i = 0; i < courseList.size(); i++) {
res[i] = courseList.get(i);
}
return res;
}
}
}
|
DFS
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
48
| class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> edgeList = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++) {
edgeList.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
int from = prerequisite[1], to = prerequisite[0];
edgeList.get(from).add(to);
}
Stack<Integer> courseStack = new Stack<>();
int[] visitStatuses = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!dfs(edgeList, courseStack, i, visitStatuses)) {
return new int[0];
}
}
int[] res = new int[courseStack.size()];
int index = 0;
while (!courseStack.isEmpty()) {
res[index++] = courseStack.pop();
}
return res;
}
private boolean dfs(List<List<Integer>> edgeList, Stack<Integer> courseStack, int course, int[] visitStatuses) {
if (visitStatuses[course] == 2) {
return true;
}
if (visitStatuses[course] == 1) {
return false;
}
visitStatuses[course] = 1;
for (int to : edgeList.get(course)) {
if (!dfs(edgeList, courseStack, to, visitStatuses)) {
return false;
}
}
visitStatuses[course] = 2;
courseStack.push(course);
return true;
}
}
|
References
210. Course Schedule II
剑指 Offer II 113. 课程顺序