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:
1 <= numCourses <= 10^5struct 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);
}