classSolution: defcheckIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: g = [[] for _ inrange(numCourses)] indgree = [0] * numCourses isPre = [[False] * numCourses for _ inrange(numCourses)] for p in prerequisites: indgree[p[1]] += 1 g[p[0]].append(p[1])
q = [] for i inrange(numCourses): if indgree[i] == 0: q.append(i) whilelen(q) > 0: cur = q[0] q.pop(0) for ne in g[cur]: isPre[cur][ne] = True for i inrange(numCourses): isPre[i][ne] = isPre[i][ne] or isPre[i][cur] indgree[ne] -= 1 if indgree[ne] == 0: q.append(ne) res = [] for query in queries: res.append(isPre[query[0]][query[1]]) return res
var checkIfPrerequisite = function(numCourses, prerequisites, queries) { let g = newArray(numCourses).fill(0).map(() =>newArray()); let indgree = newArray(numCourses).fill(0); let isPre = newArray(numCourses).fill(0).map(() =>newArray(numCourses).fill(false)); for (let p of prerequisites) { ++indgree[p[1]]; g[p[0]].push(p[1]); } let q = []; for (let i = 0; i < numCourses; ++i) { if (indgree[i] == 0) { q.push(i); } }
while (q.length) { let cur = q.shift(); for (let ne of g[cur]) { isPre[cur][ne] = true; for (let i = 0; i < numCourses; ++i) { isPre[i][ne] = isPre[i][ne] || isPre[i][cur]; } --indgree[ne]; if (indgree[ne] == 0) { q.push(ne); } } } res = []; for (let query of queries) { res.push(isPre[query[0]][query[1]]); } return res; };
复杂度分析
时间复杂度：O(\textit{numCourses}^2 + n + m)，其中 numCourses 为课程数，n 为题目给出的先决条件的数目，m 为题目给出的查询数，其中通过计算矩阵 isPre 的时间复杂度为 O(\textit{numCourses}^2)，构建有向图的复杂度为 O(\textit{numCourses} + n)，处理每一个查询的复杂度为 O(1)，共有 m 个查询，所以总的查询时间复杂度为 O(m)。
「方法一」中「拓扑排序」的实现同样可以通过「深度优先搜索」来实现。与「广度优先搜索」计入每一个点的出度不同，通过「深度优先搜索」需要记录每一个点是否被访问，我们用 vi}[x] 来表示课程 x 是否被访问，初始时为 False。
我们从编号小到大遍历全部节点，若节点 i 未被访问，则进入「深度优先搜索」流程：
若当前节点 x 已被访问，则直接返回。
若当前节点 x 未被访问，将访问状态设为已访问，然后继续对其全部后继节点递归进行「深度优先搜索」流程。将节点 x 置为其每一个后继节点 y 的先决条件，有 isPre}[x][y] = \text{True，以及对于每一个以 y 为先决条件的节点 t，节点 x 同样为 t 的先决条件，有 isPre}[x][t] = \text{True。
publicclassSolution { public IList<bool> CheckIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { IList<int>[] g = new IList<int>[numCourses]; for (int i = 0; i < numCourses; i++) { g[i] = new List<int>(); } bool[] vi = newbool[numCourses]; bool[][] isPre = newbool[numCourses][]; for (int i = 0; i < numCourses; i++) { isPre[i] = newbool[numCourses]; } foreach (int[] p in prerequisites) { g[p[0]].Add(p[1]); } for (int i = 0; i < numCourses; ++i) { DFS(g, isPre, vi, i); } IList<bool> res = new List<bool>(); foreach (int[] query in queries) { res.Add(isPre[query[0]][query[1]]); } return res; }
publicvoidDFS(IList<int>[] g, bool[][] isPre, bool[] vi, int cur) { if (vi[cur]) { return; } vi[cur] = true; foreach (int ne in g[cur]) { DFS(g, isPre, vi, ne); isPre[cur][ne] = true; for (int i = 0; i < isPre.Length; ++i) { isPre[cur][i] = isPre[cur][i] | isPre[ne][i]; } } } }
classSolution: defcheckIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: g = [[] for _ inrange(numCourses)] vi = [False] * numCourses isPre = [[False] * numCourses for _ inrange(numCourses)] for p in prerequisites: g[p[0]].append(p[1])
defdfs(cur): if vi[cur]: return vi[cur] = True for ne in g[cur]: dfs(ne) isPre[cur][ne] = True for i inrange(numCourses): isPre[cur][i] = isPre[cur][i] | isPre[ne][i]
for i inrange(numCourses): dfs(i) res = [] for query in queries: res.append(isPre[query[0]][query[1]]) return res
funccheckIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool { g := make([][]int, numCourses) vi := make([]bool, numCourses) isPre := make([][]bool, numCourses) for i := 0; i < numCourses; i++ { isPre[i] = make([]bool, numCourses) g[i] = []int{} } for _, p := range prerequisites { g[p[0]] = append(g[p[0]], p[1]) }
for i := 0; i < numCourses; i++ { dfs(g, isPre, vi, i) } res := []bool{} for _, query := range queries { res = append(res, isPre[query[0]][query[1]]) } return res }
funcdfs(g [][]int, isPre [][]bool, vi []bool, cur int) { if vi[cur] { return } vi[cur] = true for _, ne := range g[cur] { dfs(g, isPre, vi, ne) isPre[cur][ne] = true for i := 0; i < len(isPre); i++ { isPre[cur][i] = isPre[cur][i] || isPre[ne][i] } } }
var checkIfPrerequisite = function(numCourses, prerequisites, queries) { let g = newArray(numCourses).fill(0).map(() =>newArray()); let vi = newArray(numCourses).fill(false); let isPre = newArray(numCourses).fill(0).map(() =>newArray(numCourses).fill(false)); for (let p of prerequisites) { g[p[0]].push(p[1]); } for (let i = 0; i < numCourses; ++i) { dfs(g, isPre, vi, i); } res = []; for (let query of queries) { res.push(isPre[query[0]][query[1]]); } return res; };
var dfs = function(g, isPre, vi, cur) { if (vi[cur]) { return; } vi[cur] = true; for (let ne of g[cur]) { dfs(g, isPre, vi, ne); isPre[cur][ne] = true; for (let i = 0; i < isPre.length; ++i) { isPre[cur][i] = isPre[cur][i] | isPre[ne][i]; } } }
复杂度分析
时间复杂度：O(\textit{numCourses}^2 + n + m)，其中 numCourses 为课程数，n 为题目给出的先决条件的数目，m 为题目给出的查询数，其中计算矩阵 isPre 的时间复杂度为 O(\textit{numCourses}^2)，构建有向图的复杂度为 O(\textit{numCourses} + n)，处理每一个查询的复杂度为 O(1)，共有 m 个查询，所以总的查询时间复杂度为 O(m)。
