Medium
其实删入度的那个方法就是Kahn's algorithm.所以基本上这类题我是会了。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] res = new int[numCourses];
Map<Integer, Set<Integer>> neighbors = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();
for (int i = 0; i < numCourses; i++){
indegree.put(i, 0);
}
for (int[] prerequisite : prerequisites){
neighbors.put(prerequisite[1], new HashSet<Integer>());
indegree.put(prerequisite[0], indegree.get(prerequisite[0]) + 1);
}
for (int[] prerequisite : prerequisites){
neighbors.get(prerequisite[1]).add(prerequisite[0]);
}
Queue<Integer> queue = new LinkedList<>();
for (Integer i : indegree.keySet()){
if (indegree.get(i) == 0){
queue.offer(i);
}
}
int index = 0;
int count = 0;
while(!queue.isEmpty()){
Integer i = queue.poll();
count++;
res[index++] = i;
if (neighbors.containsKey(i)){
for (Integer nei : neighbors.get(i)){
indegree.put(nei, indegree.get(nei) - 1);
if (indegree.get(nei) == 0){
queue.offer(nei);
}
}
}
}
if (count != numCourses){
return new int[]{};
}
return res;
}
}
