解題程式碼

var canFinish = function (numCourses, prerequisites) {
  let queue = [];
  const graph = new Map();
  const indegrees = new Array(numCourses).fill(0);

  for (const [e, v] of prerequisites) {
    // v: 需先修的課
    if (graph.has(v)) {
      graph.get(v).push(e);
    } else {
      graph.set(v, [e]);
    }
    indegrees[e]++;
  }

  for (let i = 0; i < indegrees.length; i++) {
    if (indegrees[i] === 0) queue.push(i);
  }

  while (queue.length) {
    const v = queue.shift();
    if (!graph.has(v)) continue;

    for (const e of graph.get(v)) {
      indegrees[e]--;
      if (indegrees[e] === 0) queue.push(e);
    }
  }

  return !indegrees.find((e) => e === 1);
};

解題思路、演算法

題目中有段 You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.，就是在講節點和邊的關係，以 [1,0] 來說，就是 1 => 0，0 沒有任何修課限制。

test case: prerequisites = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 4]]。

不可能完成的情況為圖中出現環，例如題目給的範例 2。

解題作法是可以先用一個 hashMap，key 儲存的是各課程，value 為陣列，儲存它需要先修的課。並另外用一個陣列去儲存各課程所需的先修課數目。

然後用 queue 記錄當前可以修的課程，每彈出一個課程，當作修完課，就將陣列中先修課有該課的課程值 -1。

當 queue 清空時，若 hashMap 中還有 value > 0，就代表課沒辦法上完，結果為 false。又或是可以用一個陣列去儲存已經上過的課(queue 彈出的元素)，若數目和 numCourses 不同，也代表課沒辦法上完，結果為 false。

LeetCode 官方題解說明得很詳細，推薦參考，附在參考資料連結。

解法的時間、空間複雜度

時間複雜度: O(E + V)
空間複雜度: O(E + V)

參考資料

207. Course Schedule 课程表 【LeetCode 力扣官方题解】

图文详解面试常考算法 —— 拓扑排序

「拓撲順序」是指一張有向圖經過「拓撲排序」後，每一個點的先後順序。一張圖有許多種「拓撲順序」。只要不違背圖上每一條邊的先後規定，要怎麼排列圖上的點都行。