## 210. Course Schedule II

There are a total of `n`

courses you have to take labelled from `0`

to `n - 1`

.

Some courses may have `prerequisites`

, for example, if `prerequisites[i] = [a`

this means you must take the course _{i}, b_{i}]`b`

before the course _{i}`a`

._{i}

Given the total number of courses `numCourses`

and a list of the `prerequisite`

pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return **any** of them. If it is impossible to finish all courses, return **an empty array**.

**Example 1:**

Input:numCourses = 2, prerequisites = [[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:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]Output:[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].

**Example 3:**

Input:numCourses = 1, prerequisites = []Output:[0]

**Constraints:**

`1 <= numCourses <= 2000`

`0 <= prerequisites.length <= numCourses * (numCourses - 1)`

`prerequisites[i].length == 2`

`0 <= a`

_{i}, b_{i}< numCourses`a`

_{i}!= b_{i}- All the pairs
`[a`

are_{i}, b_{i}]**distinct**.

## Rust Solution

```
struct Solution;
use std::collections::VecDeque;
impl Solution {
fn find_order(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
let mut res = vec![];
let n = num_courses as usize;
let mut edges: Vec<Vec<usize>> = vec![vec![]; n];
let mut indegrees: Vec<usize> = vec![0; n];
let mut queue: VecDeque<usize> = VecDeque::new();
for e in prerequisites {
let u = e[1] as usize;
let v = e[0] as usize;
edges[u].push(v);
indegrees[v] += 1;
}
for u in 0..n {
if indegrees[u] == 0 {
queue.push_back(u);
}
}
while let Some(u) = queue.pop_front() {
res.push(u);
for &v in &edges[u] {
indegrees[v] -= 1;
if indegrees[v] == 0 {
queue.push_back(v);
}
}
}
if res.len() == n {
res.into_iter().map(|v| v as i32).collect()
} else {
vec![]
}
}
}
#[test]
fn test() {
let num_courses = 2;
let prerequisites: Vec<Vec<i32>> = vec_vec_i32![[1, 0]];
let res = vec![0, 1];
assert_eq!(Solution::find_order(num_courses, prerequisites), res);
let num_courses = 4;
let prerequisites: Vec<Vec<i32>> = vec_vec_i32![[1, 0], [2, 0], [3, 1], [3, 2]];
let res = vec![0, 1, 2, 3];
assert_eq!(Solution::find_order(num_courses, prerequisites), res);
}
```

Having problems with this solution? Click here to submit an issue on github.