207. 课程表 : boolean

BFS

  1. function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  2.     let edges: number[][] = Array.from({ length: numCourses }, () => ([]));
  3.     let indeg = new Array(numCourses).fill(0);
  5.     for (let [b, a] of prerequisites) {
  6.         edges[a].push(b);
  7.         indeg[b] += 1;
  8.     }
  10.     let queue = [];
  11.     for (let i = 0; i < numCourses; i++) {
  12.         if (!indeg[i]) {
  13.             queue.push(i);
  14.         }
  15.     }
  17.     let visited: number = 0;
  18.     while (queue.length) {
  19.         visited += 1;
  20.         const u = queue.shift();
  21.         for (let v of edges[u]) {
  22.             indeg[v] -= 1;
  23.             if (!indeg[v]) {
  24.                 queue.push(v);
  25.             }
  26.         }
  27.     }
  28.     return visited == numCourses;
  29. };

DFS 【逆向思维】

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    let edges: number[][] = Array.from({length: numCourses}, () => ([]));
    let visited = new Array(numCourses).fill(0);
    // 0 未搜索， 1 搜索中， 2 已完成
    let valid = true;

    for (let [b, a] of prerequisites) {
        edges[a].push(b);
    }

    // console.log(edges)
    function dfs (u: number): void {
        visited[u] = 1;
        for (let v of edges[u]) {
            let curVisited = visited[v];
            if (!curVisited) {
                dfs(v);
                if (!valid) return;
            } else if (curVisited == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }

    for (let i = 0; i < numCourses; i++) {
        if (valid && !visited[i]) {
            dfs(i);
        }
    }

    return valid;
};

210. 课程表 II | number[]

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    let edges = Array.from({ length: numCourses }, ()  => ([]));
    let indeg = new Array(numCourses).fill(0);
    for (let [b, a] of prerequisites) {
        edges[a].push(b);
        indeg[b] += 1;
    }

    let queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (!indeg[i]) {
            queue.push(i);
        }
    }

    let ans = [];
    while (queue.length) {
        const u = queue.shift();
        ans.push(u);
        for (let v of edges[u]) {
            indeg[v] -= 1;
            if (!indeg[v]) {
                queue.push(v);
            }
        }
    }
    return ans.length == numCourses ? ans : [];
};