[207. Course Schedule](https://leetcode.com/problems/course-schedule/)

### 題目描述

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 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`.

* For example, the pair [0, 1], indicates that to take course `0` you have to first take course `1`.

Return `true` if you can finish all courses. Otherwise, return `false`.

### 範例

**Example 1:**

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

**Example 2:**

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 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.

**Constraints**:

* 1 <= `numCourses` <= 2000
* 0 <= `prerequisites.length` <= 5000
* `prerequisites[i].length` == 2
* 0 <= `ai`, `bi` < `numCourses`
* All the pairs `prerequisites[i]` are **unique**.

### 解答
#### C++

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> indegree(numCourses, 0);
        for (const auto edge : prerequisites) {
            int a = edge[0];
            int b = edge[1];
            adj[b].push_back(a);
            indegree[a] ++;
        }
        // for (int i = 0; i < numCourses; i ++) {
        //     cout << indegree[i] << " ";
        // }
        // cout << endl;
        
        queue<int> frontier;
        for (int nodeID = 0; nodeID < numCourses; nodeID ++) {
            if (indegree[nodeID] == 0) {
                frontier.push(nodeID);
            }
        }
        vector<int> topologicalSort;
        while (not frontier.empty()) {
            int u = frontier.front();
            // cout << u << endl;
            frontier.pop();
            topologicalSort.push_back(u);
            for (int v : adj[u]) {
                indegree[v] --;
                if (indegree[v] == 0) {
                    frontier.push(v);
                }
            }
        }
        return topologicalSort.size() == numCourses;
    }
};

> [name=Jerry Wu][time=13 July, 2023]

#### Javascript

function canFinish(numCourses, prerequisites) {
  const graph = new Array(numCourses).fill(0).map(() => []);
  const visited = [];

  for (const [course, pre] of prerequisites) {
    graph[course].push(pre);
  }

  for (const i in graph) {
    if (!dfs(i, graph, visited)) return false;
  }

  return true;
}

function dfs(i, graph, visited) {
  if (visited[i]) return false;
  if (visited[i] === false) return true;

  visited[i] = true;
  for (const j of graph[i]) {
    if (!dfs(j, graph, visited)) return false;
  }
  visited[i] = false;

  return true;
}

> 參考討論區解答的
> [name=Marsgoat][time=13 July, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)