210. Course Schedule II

#### QUESTION:

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

``````Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
course 0. So the correct course order is [0,1] .
``````

Example 2:

``````Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
``````

Note:

``````The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
``````

#### EXPLANATION:

1. 创建int[]和list用来标记入度的个数和出度的node
2. 循环遍历条件，将对应的node的入度进行++，同时对出度进行标记
3. 找出入度为0的节点，放入到queue中
4. 当queue不为空的时候，取出该节点，并将该节点所指向的节点入度都减一
5. 如果出度的节点入度为0，那么也可以放入到queue中
6. 重复3-5步即可获取到最终的结果

#### SOLUTION:

``````class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] inDgree = new int[numCourses];
ArrayList<Integer>[] index = new ArrayList[numCourses];
for(int i = 0;i<numCourses;i++) index[i] = new ArrayList<>();
for(int i = 0;i<prerequisites.length;i++){
inDgree[prerequisites[i][0]]++;
}
ArrayList<Integer> result =new ArrayList<>();
Queue<Integer> queue = new ArrayDeque<>();
for(int i = 0;i<inDgree.length;i++) if(inDgree[i]==0) queue.offer(i);

while (!queue.isEmpty()){
int curr = queue.poll();