@TOC

# # 题目描述

``````输入：n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]

``````

``````输入：n = 2, prerequisites = [], queries = [[1,0],[0,1]]

``````

``````输入：n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]

``````

``````输入：n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]

``````

``````输入：n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]

``````

1. `2 <= n <= 100`
2. `0 <= prerequisite.length <= (n * (n - 1) / 2)`
3. `0 <= prerequisite[i][0], prerequisite[i][3] < n`
4. `prerequisite[i][0] != prerequisite[i][4]`
5. 先修课程图中没有环。
6. 先修课程图中没有重复的边。
7. `1 <= queries.length <= 10^4`
8. `queries[i][0] != queries[i][5]`

# # 解题方法

## # DFS

``````1 -> 2 -> 3 -> 4
``````

• 时间复杂度：最好情况下只需要第一次搜索的时候把路径保存下来，之后查表就行，因此时间复杂度是 O(n)；最坏情况下，查询的时候从来没有走过重复的路径（比如星型的图），时间复杂度是O(N * queries.length)。
• 空间复杂度：最省空间的时候是没有保存过重复的路径，空间复杂度是O(1)；最费空间是把所有的节点两两路径保存，空间复杂度是O(N^2)。

Python 代码如下：

``````class Solution(object):
def checkIfPrerequisite(self, n, prerequisites, queries):
"""
:type n: int
:type prerequisites: List[List[int]]
:type queries: List[List[int]]
:rtype: List[bool]
"""
self.graph = collections.defaultdict(list)
for pre in prerequisites:
self.graph[pre[0]].append(pre[1])
return [self.dfs(query[0], query[1]) for query in queries]

# start -> end ?
@functools.lru_cache
def dfs(self, start, end):
if start == end:
return True
return any(self.dfs(nxt, end) for nxt in self.graph[start])
``````

# # 日期

2020 年 6 月 1 日 —— 6月的开始，儿童节快乐！