## 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: true
Explanation: 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: false
Explanation: 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 as usize;
let v = e 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.