难度：中等

思路：

1. 显然它是一个课程图的结构，因为没有环也可以看成是森林结构
2. 对于一组 queries 最直接的方法就是以 v 作为根节点进行深搜或者广搜，能找到 u 就是 True，不能则是 False
3. 本体有多个 queries，当 queries数组很大时会超时，需要记忆化搜索

下面是我的代码：

class Solution:def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:ans = []m = {}hasJ = {}for pre in prerequisites:t = m.get(pre[1], [])t.append(pre[0])m[pre[1]] = tdef find(m, u, v):if (u, v) in hasJ:return hasJ[(u, v)]t = m.get(v, [])if u in t:return Trueif t is None:return Falsefor i in t:if find(m, u, i):hasJ[(u, v)] = Truereturn TruehasJ[(u, v)] = Falsereturn Falsefor q in queries:ans.append(find(m, q[0], q[1]))return ans

学习更优的代码：

1. defaultdict()的使用，该方法在初始化一个字典的同时可以自定义字典的value类型，例如dict = defaultdict(list)，自定义字典的value为列表（list）,当访问一个key不存在时，将会为这个key自动创建一个新的list，大小为空
2. set和set之间求并集用符号 “|”
3. @cache 装饰器（注解）缓存功能介绍
   在cache的源码中，对cache的描述是：Simple lightweight unbounded cache. Sometimes called “memoize”. 翻译成中文：简单的轻量级无限制缓存。有时也被称为“记忆化”。直接点就是，在下次以相同参数调用函数时直接返回上一次的结果，所以对于本题来说不需要像我一样设置一个记忆化数组hasJ来优化时间开销

下面是修改后的代码：

class Solution:def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:ans = []m = defaultdict(list)for pre in prerequisites:m[pre[1]].append(pre[0])@cachedef find(u, v):t = m.get(v, [])if u in t:return Truefor i in t:if find(u, i):return Truereturn Falsefor q in queries:ans.append(find(q[0], q[1]))return ans