[M] 207. 課程擋修 (Course Schedule)

輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
說明：總共有 2 門課程。要修習課程 1，你需要先修習課程 0。所以可以完成所有課程。

輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
輸出：false
說明：總共有 2 門課程。要修習課程 1，你需要先修習課程 0，並且要修習課程 0，你也需要先修習課程 1。所以無法完成所有課程。

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // 處理邊界條件，某些狀況一定可以修完直接回傳 true
 
  // 宣告目前的 in-degrees 數量、out-degree 對應的點、已完成的修課數
  // 根據 prerequisites 跑迴圈，去計算每個節點的 in-degree、out-degree 對應的點
  // 初始化一個 queue 存放當前 in-degree 為 0 的節點
 
  // 跑一個 while 迴圈直到 queue 為空
    // dequeue 當前節點並對完成修課數量計數
    // 對當前節點對應的 out-degree 的點去做入度減一，並在減完後將入度為 0 者推入 queue 中
 
  // 確認完成修課數量是否與課程數量相等，「是」則代表能完成所有課程
}

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // 處理邊界條件，某些狀況一定可以修完直接回傳 true
  if (numCourses <= 1 || prerequisites.length <= 1) {
    return true;
  }
 
  // 宣告目前的 in-degrees 數量、out-degree 對應的點、已完成的修課數
  const inDegrees = Array(numCourses).fill(0);
  const outDegreeNodes: Set<number>[] = Array.from(
    { length: numCourses },
    () => new Set()
  );
  let finishCount = 0;
 
  // 根據 prerequisites 跑迴圈，去計算每個節點的 in-degree、out-degree 對應的點
  for (let [course, preCourse] of prerequisites) {
    inDegrees[course]++;
    outDegreeNodes[preCourse].add(course);
  }
 
  // 初始化一個 queue 存放當前 in-degree 為 0 的節點
  const queue = inDegrees.reduce<number[]>((accu, curr, index) => {
    if (curr === 0) {
      accu.push(index);
    }
    return accu;
  }, []);
 
  // 跑一個 while 迴圈直到 queue 為空
  while (queue.length > 0) {
    // dequeue 當前節點並對完成修課數量計數
    const currentNode = queue.shift() as number;
    finishCount++;
 
    // 對當前節點對應的 out-degree 的點去做入度減一，並在減完後將入度為 0 者推入 queue 中
    for (let neighbor of outDegreeNodes[currentNode]) {
      inDegrees[neighbor]--;
 
      if (inDegrees[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }
 
  // 確認完成修課數量是否與課程數量相等，「是」則代表能完成所有課程
  return finishCount === numCourses;
}

const testCases = [
  {
    numCourses: 2,
    prerequisites: [[1, 0]],
    expected: true
  },
  {
    numCourses: 2,
    prerequisites: [
      [1, 0],
      [0, 1]
    ],
    expected: false
  },
  // DAG 無環
  {
    numCourses: 5,
    prerequisites: [
      [1, 0],
      [2, 1],
      [3, 2],
      [4, 3]
    ],
    expected: true
  },
  // 有環
  {
    numCourses: 4,
    prerequisites: [
      [0, 1],
      [1, 2],
      [2, 3],
      [3, 1]
    ],
    expected: false
  },
  {
    numCourses: 1,
    prerequisites: [],
    expected: true
  },
  {
    numCourses: 20,
    prerequisites: [[0, 1]],
    expected: true
  }
];
 
describe('Course Schedule', () => {
  test.each(testCases)(
    'should return $expected for numCourses = $numCourses and prerequisites = $prerequisites',
    ({ numCourses, prerequisites, expected }) => {
      expect(canFinish(numCourses, prerequisites)).toBe(expected);
    }
  );
});