207. 课程表（JS实现）

浅浅的花香味﹌ 2022-11-25 13:06 113阅读 0赞

## 1 题目 ##

> 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-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。这是不可能的。

链接：https://leetcode-cn.com/problems/course-schedule

## 2 思路 ##

**这道题就是考察拓扑排序，用于排查图里有没有环，首先建立图的邻接矩阵，然后再进行拓扑排序，逐步删除入度为0的节点**

## 3代码 ##

/** * @param {number} numCourses * @param {number[][]} prerequisites * @return {boolean} */
    var canFinish = function(numCourses, prerequisites) { 
        function Vex(value) { 
            this.val = value;
            this.firstEdge = null;
            this.in = 0;
        }
    
        const vexs = [];
    
        for (let arr of prerequisites) { 
            if (!vexs[arr[1]]) { 
                vexs[arr[1]] = new Vex(arr[1]);
            }
    
            if (!vexs[arr[0]]) { 
                vexs[arr[0]] = new Vex(arr[0]);
            }
    
            let firstEdge = vexs[arr[1]].firstEdge;
            vexs[arr[1]].firstEdge = { vex: vexs[arr[0]], next: firstEdge};
            vexs[arr[0]].in++;
        }
    
        const stack= [];
        let len = 0;
        for (let i=0; i<vexs.length; i++) { 
            if (vexs[i]) { 
                len++;
                if (vexs[i].in === 0) stack.push(vexs[i]);
            }
        }
    
        let count = 0;
        while(stack.length > 0) { 
            let currentVex = stack.pop();
            count++;
            let currentEdge = currentVex.firstEdge;
            while(currentEdge) { 
                if (--currentEdge.vex.in === 0) stack.push(currentEdge.vex);
                currentEdge = currentEdge.next;
            }
        }
    
        return len === count;
    
    };