-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCourseSchedule2.java
More file actions
45 lines (37 loc) · 1.43 KB
/
CourseSchedule2.java
File metadata and controls
45 lines (37 loc) · 1.43 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
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if(numCourses == 0) return new int[0];
int[] result = new int[numCourses];
if(prerequisites.length == 0) {
for(int i=numCourses-1; i > 0; i--) result[i] = i;
}
List<ArrayList<Integer>> G = new ArrayList<ArrayList<Integer>>();
for(int i=0; i < numCourses; i++){
G.add(i, new ArrayList<Integer>());
}
int[] indegree = new int[numCourses];
for(int[] pair : prerequisites) {
int course = pair[0];
int req = pair[1];
G.get(course).add(req);
indegree[req]++;
}
Queue<Integer> queue = new LinkedList();
int count = numCourses-1;
//Get all nodes with no incoming edges
for(int i=0; i < indegree.length; i++){
if(indegree[i] == 0) queue.offer(i);
}
//For all nodes with no incoming edges
while(!queue.isEmpty()){
int n = queue.poll(); //get node
result[count--] = n; //add node to list;
for(int edge : G.get(n)){ // For each adjacent node connected to node with edge
indegree[edge]--; // remove edge from graph
if(indegree[edge] == 0) queue.offer(edge); //if no other edges, add node to queue
}
}
if(count > 0) return new int[0];
return result;
}
}