1462.课程表IV

链接：1462.课程表IV
难度：Medium
标签：深度优先搜索、广度优先搜索、图、拓扑排序
简介：你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。

题解 1 - rust

• 编辑时间：2023-09-12
• 执行用时：60ms
• 内存消耗：3.11MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn check_if_prerequisite(
        num_courses: i32,
        prerequisites: Vec<Vec<i32>>,
        queries: Vec<Vec<i32>>,
    ) -> Vec<bool> {
        use std::collections::{HashMap, HashSet};
        let num_courses = num_courses as usize;
        let mut parr = vec![HashSet::<usize>::new(); num_courses];
        for item in prerequisites {
            let (item1, item2) = (item[0] as usize, item[1] as usize);
            parr[item2].insert(item1);
        }
        let mut m = HashMap::new();
        fn dfs(m: &mut HashMap<usize, HashSet<usize>>, parr: &Vec<HashSet<usize>>, idx: usize) {
            if m.contains_key(&idx) {
                return;
            }
            let mut item = HashSet::new();
            for p in &parr[idx] {
                item.insert(*p);
                dfs(m, parr, *p);
                for p in m.get(p).unwrap() {
                    item.insert(*p);
                }
            }
            m.insert(idx, item);
        }
        for idx in 0..num_courses {
            dfs(&mut m, &parr, idx);
        }
        queries
            .into_iter()
            .map(|query| {
                m.get(&(query[1] as usize))
                    .unwrap()
                    .contains(&(query[0] as usize))
            })
            .collect()
    }
}

题解 2 - cpp

• 编辑时间：2023-09-12
• 执行用时：816ms
• 内存消耗：164.73MB
• 编程语言：cpp
• 解法介绍：提前预处理。

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<unordered_set<int>> parr(numCourses);
        for (auto &item : prerequisites) {
            parr[item[1]].insert(item[0]);
        }
        unordered_map<int, unordered_set<int>> m;
        function<unordered_set<int>(int)> find_parent = [&](int idx) {
            if (m.count(idx)) return m[idx];
            unordered_set<int> res(parr[idx].begin(), parr[idx].end());
            if (parr[idx].size()) {
                for (auto &p : parr[idx]) {
                    for (auto &item : find_parent(p)) {
                        res.insert(item);
                    }
                }
            }
            return m[idx] = res;
        };
        for (int idx = 0; idx < numCourses; idx++) {
            parr[idx] = find_parent(idx);
        }
        vector<bool> res;
        for (auto &query : queries) {
            res.push_back(parr[query[1]].count(query[0]));
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-09-12
• 执行用时：80ms
• 内存消耗：19.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        parr = [set() for _ in range(numCourses)]
        for [item1, item2] in prerequisites:
            parr[item2].add(item1)
        @cache
        def find_parent(idx: int) -> set:
            res = set(parr[idx])
            if len(parr[idx]):
                for p in parr[idx]:
                    res |= find_parent(p)
            return res
        for idx in range(numCourses):
            parr[idx] = find_parent(idx)
        return [query[0] in parr[query[1]] for query in queries]