207. Course Schedule

Leetcode link

题目简介

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */

题目给我们一个数字 numCourses 表示当前有从 0 到 numCourses - 1 共 numCourses 门课程

以及一个数组 prerequisites，其中有多个 [a, b] 组合，表示想上 a 课程必须先上 b

题目要求我们返回是否能在 prerequisites 的约束下学完所有课程

解题思路

我们考虑两种情况：

// 1. 同一路径下出现循环
a -> b -> c -> a     

// 2. 同一路径下没有循环
a -> b -> c
a -> d -> c

综上，我们知道要满足不能学完所有课程的条件就是在当前的学习路径上存在循环

所以，我们可以设计一套深度遍历机制，来模拟不同的合法学习路径并且记录路径中学习的课程

如果在该路径中出现过的课程又出现了，表示存在循环，不可能学习完所有课程

反之如果我们遍历完所有的课程后都没有循环，则表示可以学习完所有课程

Javascript

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
    // Saves all courses that can only be taken after completing the current course
    const arr = Array.from({ length: numCourses }, _ => new Array())
    for (const [course, prerequisite] of prerequisites) {
        arr[prerequisite].push(course)
    }
    const finished = new Array(numCourses).fill(false)

    // return if there is a cycle
    const dfs = (course, path) => {
        finished[course] = true
        path.push(course)

        for (const nextCourse of arr[course]) {
            if (!finished[nextCourse]) {
                if (dfs(nextCourse, path)) {
                    return true
                }
            } else if(path.includes(nextCourse)) {
                return true
            }
        }

        path.pop()
        return false
    }

    for (let i = 0; i < numCourses; i++) {
        if (!finished[i] && dfs(i, [])) {
            return false
        }
    }

    return true
};