-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathCourseScheduleII.java
More file actions
60 lines (54 loc) · 1.98 KB
/
CourseScheduleII.java
File metadata and controls
60 lines (54 loc) · 1.98 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
48
49
50
51
52
53
54
55
56
57
58
59
60
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> graphMap = new HashMap<Integer, List<Integer>>();
int[] degreeMap = constructMap(graphMap, numCourses, prerequisites);
List<Integer> inDegreeZero = new ArrayList<Integer>();
for (int i = 0; i < degreeMap.length; i++) {
if (degreeMap[i] == 0) {
inDegreeZero.add(i);
}
}
int[] order = new int[numCourses];
int orderIdx = 0;
while (inDegreeZero.size() > 0) {
int curr = inDegreeZero.remove(inDegreeZero.size() - 1);
order[orderIdx] = curr;
orderIdx += 1;
if (graphMap.containsKey(curr) == false) {
continue;
}
List<Integer> currNei = graphMap.get(curr);
for (int i = 0; i < currNei.size(); i++) {
degreeMap[currNei.get(i)] -= 1;
if (degreeMap[currNei.get(i)] == 0) {
inDegreeZero.add(currNei.get(i));
}
}
graphMap.remove(curr);
}
if (graphMap.size() > 0) {
return new int[0];
} else {
return order;
}
}
public int[] constructMap(Map<Integer, List<Integer>> graphMap, int numCourses, int[][] pre) {
int[] degreeMap = new int[numCourses];
int rows = pre.length;
for (int i = 0; i < rows; i++) {
int key = pre[i][1];
if (graphMap.containsKey(key)) {
List<Integer> curr = graphMap.get(key);
curr.add(pre[i][0]);
degreeMap[pre[i][0]] += 1;
graphMap.put(key, curr);
} else {
List<Integer> newList = new ArrayList<Integer>();
newList.add(pre[i][0]);
degreeMap[pre[i][0]] += 1;
graphMap.put(key, newList);
}
}
return degreeMap;
}
}