## 207. Course Schedule

There are a total of `numCourses`

courses you have to take, labeled from `0`

to `numCourses-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**, is it possible for you to finish all courses?

**Example 1:**

Input:numCourses = 2, prerequisites = [[1,0]]Output:trueExplanation:There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

**Example 2:**

Input:numCourses = 2, prerequisites = [[1,0],[0,1]]Output:falseExplanation:There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

**Constraints:**

- 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.
`1 <= numCourses <= 10^5`

## Rust Solution

```
struct Solution;
impl Solution {
fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
let n = num_courses as usize;
let mut indegrees: Vec<i32> = vec![0; n];
let mut edges: Vec<Vec<usize>> = vec![vec![]; n];
let mut queue: Vec<usize> = vec![];
let mut res: Vec<usize> = vec![];
for e in prerequisites {
let u = e[1] as usize;
let v = e[0] as usize;
indegrees[v] += 1;
edges[u].push(v);
}
for u in 0..n {
let indegree = indegrees[u];
if indegree == 0 {
queue.push(u);
}
}
while let Some(u) = queue.pop() {
res.push(u);
while let Some(v) = edges[u].pop() {
indegrees[v] -= 1;
if indegrees[v] == 0 {
queue.push(v);
}
}
}
res.len() == n
}
}
#[test]
fn test() {
let num_courses = 2;
let prerequisites: Vec<Vec<i32>> = vec_vec_i32![[1, 0]];
let res = true;
assert_eq!(Solution::can_finish(num_courses, prerequisites), res);
let num_courses = 2;
let prerequisites: Vec<Vec<i32>> = vec_vec_i32![[1, 0], [0, 1]];
let res = false;
assert_eq!(Solution::can_finish(num_courses, prerequisites), res);
}
```

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