forked from varunu28/LeetCode-Java-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCourse Schedule II.java
More file actions
47 lines (38 loc) · 1.33 KB
/
Course Schedule II.java
File metadata and controls
47 lines (38 loc) · 1.33 KB
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 {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] prerequisite : prerequisites) {
map.computeIfAbsent(prerequisite[0], k -> new ArrayList<>()).add(prerequisite[1]);
}
boolean[] registered = new boolean[numCourses];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < numCourses; i++) {
if (!isDeadlock(i, map, stack, registered, new boolean[numCourses])) {
return new int[]{};
}
}
int[] ans = new int[numCourses];
int idx = numCourses - 1;
while (!stack.isEmpty()) {
ans[idx--] = stack.pop();
}
return ans;
}
private boolean isDeadlock(int c1, Map<Integer, List<Integer>> map, Stack<Integer> stack, boolean[] registered, boolean[] visited) {
if (registered[c1]) {
return true;
}
if (visited[c1]) {
return false;
}
visited[c1] = true;
for (Integer prereq : map.getOrDefault(c1, new ArrayList<>())) {
if (!isDeadlock(prereq, map, stack, registered, visited)) {
return false;
}
}
registered[c1] = true;
stack.push(c1);
return true;
}
}