广度优先搜索
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
//存储答案
int[] result=new int[numCourses];
//存储入度
int[] input=new int[numCourses];
//存储答案的下标
int index=0;
Queue<Integer>que=new LinkedList<>();
//计算入度
for(int[]temp:prerequisites){
input[temp[0]]++;
}
//入度为0的入队
for(int i=0;i<numCourses;i++){
if(input[i]==0){
que.add(i);
}
}
//开始遍历 符合条件放入队列
while(!que.isEmpty()){
int node=que.poll();
result[index++]=node;
for(int[]temp:prerequisites){
if(temp[1]==node){//从node出发判断
input[temp[0]]--;
if(input[temp[0]]==0){//每次对input操作之后再判断
que.add(temp[0]);
}
}
}
}
if(index!=numCourses){
return new int[0];
}
return result;
}
}
