#207 Course Schedule

同步發佈於 Github repo

題目難度：Medium

題目敘述：

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

題目解答：

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
const canFinish = (numCourses, prerequisites) => {
  let courses = [];
  let prereqCounts = [];
  let temp;
        
  for(let i = 0; i < numCourses; i++) {
    courses.push(new Set());
  }
    
  for(let i = 0; i < prerequisites.length; i++) {
    courses[prerequisites[i][1]].add(prerequisites[i][0]);
  }
    
  for(let i = 0; i < numCourses; i++) {
    prereqCounts[i] = 0;
  }
    
  for(let i = 0; i < numCourses; i++) {
    temp = Array.from(courses[i]);

    for(let j = 0; j < temp.length; j++) {
      prereqCounts[temp[j]]++;
    }
  }
    
  for(let i = 0; i < numCourses; i++) {
    let j;

    for(j = 0; j < numCourses; j++) {
      if(prereqCounts[j] === 0) {
        break;
      }
    }
        
    if (j === numCourses) {
      return false;
    }
    
    prereqCounts[j] = -1;
    temp = Array.from(courses[j]);
    for (let k = 0; k < temp.length; k++) {
      prereqCounts[temp[k]]--;
    }
  }
    
  return true;
};

題目連結：207. Course Schedule

解題說明：

今天是第 16 天，又是新的篇章開始了！
接下來的主題都會越來越難，像這次是 graph，我就找不到難度 Easy 的題目了...
沒辦法，這次就直接從難度 Medium 的 207. Course Schedule 開始吧～

題意把有向圖包裝成課程表，要我們判斷某堂課要求先修的課所形成的圖，能不能讓學生順利修完所有的課，
像是範例給 2, [[1,0],[0,1]] 說明要修 課程 1 要先修 課程 0，但又說要修課程 0 要先修 課程 1，所以不合理，
那說這麼多，其實就是要考有像圖中有沒有 cycle ，
如果有 cycle 那就是不合理，回傳 false，反之回傳 true。

這題我們使用 拓墣排序 + DFS 來解～
詳細步驟將在下方說明！

解題步驟：

• 步驟 1.
  courses 是一個存 Set 的陣列，是用來建有向圖的，
  prereqCounts 則是記錄圖上每一個點目前仍被多少條邊連到，下一個步驟會說明，算是拓墣排序會用到的變數。

我們先初始化 courses 成一堆 Set，
然後將 courses[prerequisites[i][1]] 一一加入 prerequisites[i][0] 這些先修課。

let courses = [];
let prereqCounts = [];
let temp;
        
for(let i = 0; i < numCourses; i++) {
  courses.push(new Set());
}
    
for(let i = 0; i < prerequisites.length; i++) {
  courses[prerequisites[i][1]].add(prerequisites[i][0]);
}

• 步驟 2.
  先將 prereqCounts 初始化為 0，代表每個點預設被 0 條邊連到，
  然後使用 Array.from 將 Set 轉成 Array，最後計算每個點上累積有多少條邊連著。

for(let i = 0; i < numCourses; i++) {
  prereqCounts[i] = 0;
}
    
for(let i = 0; i < numCourses; i++) {
  temp = Array.from(courses[i]);

  for(let j = 0; j < temp.length; j++) {
    prereqCounts[temp[j]]++;
  }
}

• 步驟 3.
  這個步驟基本上就是實作拓墣排序，
  j 代表尋找沒有被任何邊連向的點，如果不幸最後 j === numCourses 就代表這個圖有環，
  剩下詳細步驟請參閱 拓墣排序 這篇，裡面有詳細且一步步的圖，讀完即可！
  完成！

for(let i = 0; i < numCourses; i++) {
  let j;

  for(j = 0; j < numCourses; j++) {
    if(prereqCounts[j] === 0) {
      break;
    }
  }
        
  if (j === numCourses) {
    return false;
  }
    
  prereqCounts[j] = -1;
  temp = Array.from(courses[j]);
  for(let k = 0; k < temp.length; k++) {
    prereqCounts[temp[k]]--;
  }
}
    
return true;