LeetCode 1136. Parallel Courses

Problem Statement

use std::collections::{HashMap, HashSet};
use std::collections::VecDeque;

impl Solution {
    pub fn minimum_semesters(n: i32, relations: Vec<Vec<i32>>) -> i32 {
        let mut in_degrees = vec![0; n as usize + 1];
        let mut map: HashMap<i32, HashSet<i32>> = HashMap::new();
        for r in &relations {
            map.entry(r[0]).or_insert(HashSet::new());
            map.get_mut(&r[0]).unwrap().insert(r[1]);
            in_degrees[r[1] as usize] += 1;
        }

        let mut q = VecDeque::new();
        let (mut ans, mut sum) = (0, 0);
        for i in 1..n + 1 {
            if in_degrees[i as usize] == 0 {
                q.push_back(i);
            }
        }

        while !q.is_empty() {
            let size = q.len();
            sum += size;
            for _i in 0..size {
                let cur = q.front().unwrap().clone();
                q.pop_front();
                if !map.contains_key(&cur) {
                    continue;
                }
                for next in map.get(&cur).unwrap() {
                    in_degrees[*next as usize] -= 1;
                    if in_degrees[*next as usize] == 0 {
                        q.push_back(*next);
                    }
                }
            }
            ans += 1;
        }
        if sum == n as usize {
            return ans;
        } else {
            return -1;
        }
    }
}