-
Notifications
You must be signed in to change notification settings - Fork 0
/
July18_2020.java
48 lines (34 loc) · 1.62 KB
/
July18_2020.java
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
// Course Schedule II => classic example of Topological Sorting.
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] depDegrees = new int[numCourses]; // no of dependencies
HashMap<Integer, List<Integer>> graph = new HashMap<>(); // graph adjancy list
for(int[] lst : prerequisites){
int master = lst[1]; // depends on
int slave = lst[0]; // dependent
depDegrees[slave]++; // update the dependency
graph.putIfAbsent(master, new ArrayList<>()); // update the graph
graph.get(master).add(slave);
}
Queue<Integer> q = new LinkedList(); // queue to maintain nodes with 0 dependency
for(int i=0; i < numCourses; i++){
if(depDegrees[i] == 0){
q.offer(i); // fill the queue initially
}
}
int[] result = new int[numCourses]; // output
int counter = 0;
while(! q.isEmpty()){
int node = q.poll();
result[counter++] = node;
if(graph.containsKey(node)){ // reduces the dependent nodes by 1 as the depends on node is added to result.
for( int course : graph.get(node)) {
if(--depDegrees[course] == 0) { // if after reduction it comes to 0, then add it to the queue
q.offer(course);
}
}
}
}
return counter == numCourses ? result : new int[0];
}
}