题目描述
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
说明略。(可点击链接查看原文)
来源：LeetCode
思路
比较典型的拓扑排序题目。将每门课视为节点，课程先置条件视为路径，可以构造出一幅有向图。然后再遍历，查看是否可以遍历所有节点即可。
解法
/**
* @desc 构建有向图
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[][]} graph 有向图
*/
const build = (numCourses, prerequisites) => {
const graph = Array(numCourses).fill().map(() => new Set());
prerequisites.forEach(([start, end]) => {
graph[start].add(end);
})
return graph;
}
/**
* @desc 广度优先搜索
* @param {number[][]} graph 有向图
* @return {number} 遍历到的数目
*/
const bfs = (graph) => {
const visited = new Set();
const queue = [];
graph.forEach((nodes, index) => {
nodes.size === 0 && queue.push(index);
})
while (queue.length) {
const node = queue.pop();
visited.add(node);
for (let i = 0; i < graph.length; i++) {
if (visited.has(i)) continue;
graph[i].delete(node);
graph[i].size === 0 && queue.push(i);
}
}
return visited.size;
}
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
const canFinish = (numCourses, prerequisites) => {
const graph = build(numCourses, prerequisites);
return bfs(graph) === numCourses;
};