Skip to main content

207. Course Schedule

分析

第一遍写的时候, map 的语法没用对,注意一定要走 get set,而不用对象来取值
  • BFS 解法

题解

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
// 构建临接表
const adjacencyLists: Map<number, number[]> = new Map()
for (const prerequisite of prerequisites) {
// [1, 0] 1 -> 0
const [a, b] = prerequisite
const prerequisiteList = adjacencyLists.get(a)
if (prerequisiteList) {
prerequisiteList.push(b)
} else {
adjacencyLists.set(a, [b])
}
}

const memoSet = new Set()
const canFinishCourseList = new Set()

const dfs = (key: number) => {
if (canFinishCourseList.has(key)) {
return true
}
if (memoSet.has(key)) {
return false
}
memoSet.add(key)
const adjacencyList = adjacencyLists.get(key) || []
for (const nextKey of adjacencyList) {
const res = dfs(nextKey)
if (!res) {
return false
}
canFinishCourseList.add(nextKey)
}
memoSet.delete(key)
return true
}

for (const [key] of adjacencyLists) {
memoSet.clear()
const res = dfs(key)
if (!res) {
return false
}
}

return true
};