_0210_course_schedule_ii.rs

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);
}